hdu 2063 二分图—最大匹配
http://acm.hdu.edu.cn/showproblem.php?pid=2063
设G=(V,E)是一个无向图。如顶点集V可分区为两个互不相交的子集V1,V2之并，并且图中每条边依附的两个顶点都分属于这两个不同的子集。则称图G为二分图。二分图也可记为G=(V1,V2,E)。
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的子集中边数最大的子集称为图的最大匹配问题(maximal matching problem)
图的点覆盖：寻找一个点集，使得图中每一条边至少有一点在该点集中
二分图的最小点覆盖 = 最大匹配
图的独立集：寻找一个点集，其中任意两点在图中无对应边
一般图的最大独立集是NP完全问题
二分图的最大独立集 = 图的点数-最大匹配
图的路径覆盖：用不相交路径覆盖有向无环图的所有顶点
二分图的最小路径覆盖 = 节点数-最大匹配
匈牙利算法：用增广路求最大匹配的方法
若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。（M为一个匹配）
由增广路的定义可以推出下述三个结论：
1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
2－将M和P进行异或操作(去同存异)可以得到一个更大的匹配M’。
3－M为G的最大匹配当且仅当不存在M的增广路径。
算法描述：
(1)置M为空
(2)找出一条增广路径P，通过异或操作获得更大的匹配M’代替M
(3)重复(2)操作直到找不出增广路径为止
#include<stdio.h>#include<string.h>#define N 505int link[N],flag[N],map[1005][2],K;int Find(int x){ int i,temp; for(i=0;i<K;i++){ if(map[i][0]==x&&flag[map[i][1]]==0){ temp=link[map[i][1]]; link[map[i][1]]=x; flag[map[i][1]]=1; //标记访问过的点，防止出现死循环和重复计算 if(temp==0||Find(temp)==1) return 1; link[map[i][1]]=temp; } } return 0;}int main(){ int n,m,i,cnt; while(scanf("%d",&K),K){ scanf("%d%d",&n,&m); memset(link,0,sizeof(link)); for(i=0;i<K;i++){ scanf("%d%d",&map[i][0],&map[i][1]); } for(i=1,cnt=0;i<=n;i++){ //每个点只需要查找一遍：若从某一点开始找不到增广路， memset(flag,0,sizeof(flag)); //则无论当前匹配如何改变都无法再从该点找到增广路 if(Find(i)) cnt++; } printf("%d\n",cnt); } return 0;}