【题解】UOJ #78 二分图最大匹配

二分图匹配模板题，跑一遍增广路即可求得配对数和配对方案。详细看我写的那个二分图最大匹配=￣ω￣=
传送门

代码：

#include <bits/stdc++.h>
using namespace std;
int n,nl,nr,m,match[1005],ans;
bool book[1005];
vector<int> g[1005];
bool dfs(int u)
{
    for(vector<int>::iterator i=g[u].begin();i!=g[u].end();i++)
        if(!book[*i])
        {
            book[*i]=1;
            if(match[*i]==0||dfs(match[*i])){match[u]=*i,match[*i]=u;return 1;}
        }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>nl>>nr>>m,n=nl+nr;
    for(int i=1,u,v;i<=m;i++)cin>>u>>v,v+=nl,g[u].push_back(v),g[v].push_back(u);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)book[j]=0;
        if(!match[i])if(dfs(i))ans++;
    }
    cout<<ans<<endl;
    for(int i=1;i<=nl;i++)cout<<(match[i]==0?0:match[i]-nl)<<' ';
    return 0;
}