二分图的最大团问题

定义&求法

在一个无向图G中，选择一个最大点集$V$，使$V$中的点两两相等。
最大团的点的数量=$G^{\prime }$最大独立集
其中，$G^{\prime }$是无向图的补图，是指用跟$G$完全相同的点先构成一个完全图，然后删掉$G$中的边，剩下的图就是$G$的补图$G^{\prime }$

复杂度：

非多项式的时间复杂度

例题：

1.POJ3692–Kindergarten

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1005;
int g,b,m,Case=1;
int match[maxn],vis[maxn],mp[maxn][maxn];
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-48;
		c=getchar();
	}
	return s*f;
}
int dfs(int u)
{
	for (int i=1;i<=b;i++)
	{
		if (!vis[i]&&mp[u][i]==0)
		{
			vis[i]=1;
			if (match[i]==-1||dfs(match[i]))
			{
				match[i]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	while (scanf("%d%d%d",&g,&b,&m)!=EOF)
	{
		memset(match,-1,sizeof(match));
		memset(mp,0,sizeof(mp));
		if (g==0&&b==0&&m==0)
		{
			break;
		}
		for (int i=0;i<m;i++)
		{
			int x=read(),y=read();
			mp[x][y]=1;
		}
		int ans=0;
		for(int i=1; i<=g; i++)
		{
			memset(vis,0,sizeof(vis));
			ans+=dfs(i);
		}
		printf("Case %d: %d\n",Case++,b+g-ans);
	}
	return 0;
}