(step6.3.1)hdu 2063(过山车——二分图的最大匹配)
题目大意:第一行输入3个整数k，n，m。分别表示可能的组合数，女生数，男生数。在接下来的k行中，每行有两个整数a，b。表示a女生愿意和b男生匹配。
求最大匹配。
解题思路:
1)直接使用匈牙利算法即可
研究了几个小时，终于明白了。说穿了，就是你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。
代码如下：
/* * 2063_2.cpp * * Created on: 2013年8月30日 * Author: Administrator * 章泽天,我的女神!!!!!!!! */#include <iostream>using namespace std;/** * map[i][j] = 1 :表示第i个女生愿意和第几个男生匹配 * link[i] = t :表示第i个男生匹配的是女生是t * useif[i] :用来判断第i个男生是否已经匹配 * n :女生数 * m :男生数 * */const int maxn = 501;int map[maxn][maxn];int link[maxn];bool useif[maxn];int n,m;int can(int t){int i;for(i = 1 ; i <= m ; ++i){//如果这个男生没有组合&&当前女生愿意和这个男生组合if(useif[i] == 0 && map[t][i]){useif[i] = 1;//如果这一个男生还没有匹配||他对应的女生可以匹配其他的男生if(link[i] == -1 || can(link[i])){//那么就将男生i的匹配女生设置为tlink[i] = t;return 1;}}}return 0;}int maxmatch(){int num = 0;int i;memset(link,-1,sizeof(link));for(i = 1 ; i <= n ; ++i){memset(useif,0,sizeof(useif));if(can(i)){num++;}}return num;}int main(){int k;while(scanf("%d",&k)!=EOF,k){memset(map,0,sizeof(map));scanf("%d%d",&n,&m);int i;for(i = 1 ; i <= k ; ++i){int a,b;scanf("%d%d",&a,&b);map[a][b] = 1;}printf("%d\n",maxmatch());}}