题目链接：?id=3692题目大意：一些男生和女生，男生们相互都认识，女生们相互都认识，，给出男女生的认识关系，要求一个最大的集合，集合中任意两个人都互相认识，求这个最大集合的元素个数题目分析：二分图最大团问题，根据定理：二分图最大团＝原图补图的最大独立集最大独立集＝总点数－最大匹配用匈牙利算法解出原图补图的最大匹配即可算出最大团中元素个数 （注：一般图的最大团问题是NP问题）代码：#include <cstdio>#include <cstring>int const MAX = 205;int cx[MAX], cy[MAX];bool vis[MAX], map[MAX][MAX];int g, b, m;int DFS(int x){for(int y = 1; y <= b; y++){if(!vis[y] && map[x][y]){vis[y] = true;if(cy[y] == -1 || DFS(cy[y])){cy[y] = x;cx[x] = y;return 1;}}}return 0;}int MaxMatch(){int ans = 0;memset(cx, -1, sizeof(cx));memset(cy, -1, sizeof(cy));for(int i = 1; i <= g; i++){if(cx[i] == -1){memset(vis, false, sizeof(vis));ans += DFS(i);}}return ans;}int main(){int ca = 1;while(scanf("%d %d %d", &g, &b, &m) != EOF && (g + b + m)){memset(map, true, sizeof(map));for(int i = 0; i < m; i++){int u, v;scanf("%d %d", &u, &v);map[u][v] = false;}printf("Case %d: %d\n", ca ++, g + b – MaxMatch());}}
会让你的心态更平和更坦然，也会让你心无旁骛，更会让你的心灵得到解脱和抚慰。
