题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2063
匈牙利算法是基于递归的增广路算法，应用于二分图匹配问题。本题是一个匈牙利算法求二分图最大匹配的应用。对于一个待匹配的V1中的点x，可以考虑给他一个可能的V2中的点y作为匹配对象，如果这个点没有匹配过或者给y找到了新的匹配对象就可以将y作为x的正式匹配。
本题中我使用的是邻接矩阵，每次搜索增广路的时间是O(|V|^2)，所以总的时间复杂度是O(|V|^3)，总的空间复杂度是O(|V|^2)，如果用邻接表实现的话总的时间复杂度是O(|V||E|)，空间复杂度是O(|E|+|V|)。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x7ffffff 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 25 return ans*w; 26 } 27 int k,n,m; 28 const int maxn=1e3; 29 int g[maxn][maxn]; 30 int m_girl,n_boy; 31 int match[maxn],reserve_boy[maxn];//匹配结果在match中 32 bool dfs(int x)//匈牙利算法:给x找一条增广路径，也就是找一个匹配对象 33 { 34 for(int i=1;i<=n_boy;i++) 35 { 36 if(!reserve_boy[i]&&g[x][i])//男孩i还没有保留对象而且女孩x可能可以和i匹配 37 { 38 reserve_boy[i]=1;//预定男孩i，准备分给x 39 if(!match[i]||dfs(match[i])) 40 //有两种情况，(1)男孩i没有匹配对象(2)男孩有配对对象，现在尝试更换男孩i的原配对象，两种成功一个便将i赋给x 41 { 42 match[i]=x;//第i个男孩的配对对象更换或者直接设置为x 43 return true; 44 } 45 } 46 } 47 return false;//对女孩i配对失败 48 } 49 int main() 50 { 51 //freopen("input.txt","r",stdin); 52 //freopen("output.txt","w",stdout); 53 std::ios::sync_with_stdio(false); 54 while(scanf("%d",&k)==1&&k) 55 { 56 m_girl=read(),n_boy=read(); 57 mem(g,0); 58 mem(match,0); 59 int u,v; 60 f(i,1,k) 61 { 62 u=read(),v=read(); 63 g[u][v]=1;//邻接矩阵存边 64 } 65 int sum=0; 66 f(i,1,m_girl)//为每个女孩寻找配对，当前寻找成功的女孩在之后可能会更换，但是一定会配对成功 67 { 68 mem(reserve_boy,0); 69 if(dfs(i))sum++; 70 } 71 pf("%d ",sum); 72 } 73 }