男女分组（二分图匹配）

传送门

板题：一：使用邻接矩阵

#include<bits/stdc++.h>

using namespace std;

const int maxn=150;

int m,n;
int mapp[maxn][maxn],match[maxn];
bool vis[maxn];

bool dfs(int u)
{
    for(int i=m+1;i<=n;i++){
        if(mapp[u][i]&&!vis[i]){
            vis[i]=1;
            if(match[i]==0||dfs(match[i])){
                match[i]=u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d",&m,&n);
    int a,b;
    while(scanf("%d%d",&a,&b)&&a!=-1&&b!=-1){
        mapp[a][b]=1;
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        memset(vis,false,sizeof(vis));
        if(dfs(i)){
            ans++;
        }
    }
    if(!ans){
        printf("No Solution!\n");
    }else{
        printf("%d\n",ans);
        for(int i=m+1;i<=n;i++){
            if(match[i]){
                cout<<match[i]<<" "<<i<<endl;
            }
        }
    }
    return 0;
}

二：本来计划使用链式前向星实现一下，但是不能确定边数，最后还可以用白书上的vector实现啊

#include<bits/stdc++.h>

using namespace std;

const int maxn=150;

int m,n;
vector<int>mapp[maxn];
bool vis[maxn];
int match[maxn];

int dfs(int u)
{
    int len=mapp[u].size();
    for(int i=0;i<len;i++){
        int end=mapp[u][i];
        if(!vis[end]){
            vis[end]=true;
            if(match[end]==0||dfs(match[end])){
                match[end]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    scanf("%d%d",&m,&n);
    int a,b;
    while(scanf("%d%d",&a,&b)&&a!=-1&&b!=-1){
        mapp[a].push_back(b);
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        memset(vis,false,sizeof(vis));
        ans+=dfs(i);
    }
    if(ans==0){
        printf("No Solution!\n");
    }else{
        printf("%d\n",ans);
        for(int i=m+1;i<=n;i++){
            if(match[i]!=0){
                printf("%d %d\n",match[i],i);
            }
        }
    }
    return 0;
}