过山车
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11066 Accepted Submission(s): 4873 Problem Description
RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
Input
输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000 1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
Output
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
Sample Input
6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0
Sample Output
3
一个一点弯也没绕的最大二分匹配问题，用的是最经典的匈牙利算法。
这个算法我感觉不好懂，涉及到新的概念，我建议是看https://www.byvoid.com/blog/hungary/byvoid大神的讲解。
这里还有一篇http://blog.csdn.net/dark_scope/article/details/8880547可以帮助理解算法的过程，很有用！
（虽然不知道为什么这么做..）
这份解题报告的重点放在注释和解释流程上..（算法的原理我就真不知道了..）
#include#include #define maxn 505int G[maxn][maxn];int match[maxn];//match[i] = j 表示i和j匹配 int packed[maxn];//packed[i]表示i被选入增广路 bool find(int start,int N)//从start点能不能找到增广路 { for(int i = 1 ; i <= N ; ++i)//所有男生 { if(G[start][i] == 1 && packed[i] == 0) //有联系并且没有被入增广路 { packed[i] = 1;//加入增广路 if(match[i] == 0 || find(match[i],N)) //Tip 3 { match[i] = start; return true; } } } return false;}int main(){ int K,M,N; int v1,v2; while(scanf("%d",&K) != EOF) { if(K == 0) break; scanf("%d%d",&M,&N); memset(G,0,sizeof(G)); memset(match,0,sizeof(match)); int ans = 0; for(int i = 1 ; i <= K ; ++i) { scanf("%d%d",&v1,&v2); G[v1][v2] = 1; //Tip 1：不能写成G[v1][v2] = G[v2][v1] = 1? } for(int i = 1 ; i <= M ; ++i) { memset(packed,0,sizeof(packed));//Tip 2：每次查询都重置增广路 if(find(i,N))//从i出发寻找可增广路 ans++;//最大匹配边数+1 } printf("%d\n",ans); } return 0;}