给G个girl和B个boy 然后给出M个配对..表示女孩i和男孩J互相认识.并且女孩和女孩之间是相互认识的
男孩与男孩之间是相互认识的..求找到一个最大的集合..集合里面的每个人都互相认识.
做法:把不认识的标记为1,认识的标记为0,那么这个结果就是该二分图的最大独立点集.
最大独立点集的概念:找出一个集合..集合内部的每个点都不互相有边连接..
那么返回标记的1状态的话..就可以表示为每个点都有一条边与其它的点相连..就是ans
最大匹配数=最小点覆盖=n-最大点独立集
#include"stdio.h" #include"string.h" #define N 201 int map[N][N],v[N],link[N]; int n,m; int dfs(int k) { int i; for(i=1;i<=m;i++) { if(map[k][i]&&!v[i]) { v[i]=1; if(link[i]==-1||dfs(link[i])) { link[i]=k; return 1; } } } return 0; } int main() { int i,j,ans,a,b,t,tt; tt=0; while(scanf("%d%d%d",&n,&m,&t)!=-1) { if(!n&&!m&&!t) break; memset(map,1,sizeof(map)); while(t--) { scanf("%d%d",&a,&b); map[a][b]=0; } ans=0; memset(link,-1,sizeof(link)); for(i=1;i<=n;i++) { memset(v,0,sizeof(v)); if(dfs(i)) ans++; } printf("Case %d: %d\n",++tt,n+m-ans); } return 0; }