HDU【2458】Kindergarten

HDU【2458】Kindergarten

题目链接：.php?pid=2458
分析
这道题求的是最大团，同时它符合二分图的定义，可以用匈牙利算法求出该图的补图的最大的匹配数，最大团就等于该补图的顶点数减去最大的匹配数。
具体的关系如下：
二分图的最大团 = 补图的最大独立集 = 补图的顶点数 - 补图的最大匹配数

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 200 + 10;
int a[N][N],vis[N],match[N];
int g,b,m;
bool find(int i)
{for(int j = 1; j <= b; j++) {if(!vis[j] && !a[i][j]) {vis[j] = 1;if(match[j] == 0 || find(match[j])) {match[j] = i;return true;}}}return false;
}
int main()
{int T = 0;while(scanf("%d%d%d",&g,&b,&m) && (g + b + m)) {T++;memset(match,0,sizeof(match));memset(a,0,sizeof(a));int u,v;for(int i = 0; i < m; i++) {scanf("%d%d",&u,&v);a[u][v] = 1;}int ans = 0;for(int i = 1; i <= g; i++) {memset(vis,0,sizeof(vis));if(find(i)) ans++;}printf("Case %d: %dn",T,g + b - ans);}return 0;
}