POJ 1466 Girls and Boys (ZOJ 1137 )最大独立点集

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=137

题目大意：

n个学生，他们中有的有关系，有的没有关系，求最多可以取出几个人，使得他们之间没有关系。

思路：

复制别人的。。。。。

最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - 最大匹配数/2，然后就是匈牙利算法实现了。

#include<cstdio>

#include<cstring>

const int MAXN=500+10;

int res[MAXN],head[MAXN],len;

bool vis[MAXN];

struct edge

{

	int to,next;

}e[MAXN*MAXN];

void add(int from,int to)

{

	e[len].to=to;

	e[len].next=head[from];

	head[from]=len++;

}

bool find(int a)

{

	for(int i=head[a];i!=-1;i=e[i].next)

	{

		int id=e[i].to;

		if(!vis[id])

		{

			vis[id]=true;

			if(res[id]==0 || find(res[id]) )

			{

				res[id]=a;

				return true;

			}

		}

	}

	return false;

}

int main()

{

	int n;

	while(~scanf("%d",&n))

	{

		memset(res,0,sizeof(res));

		memset(head,-1,sizeof(head));

		len=0;

		for(int i=0;i<n;i++)

		{

			int x,cnt;

			scanf("%d: (%d)",&x,&cnt);

			for(int j=0;j<cnt;j++)

			{

				int to;

				scanf("%d",&to);

				add(x,to);

			}

		}

		int ans=0;

		for(int i=0;i<n;i++)

		{

			memset(vis,0,sizeof(vis));

			if(find(i)) ans++;

		}

		printf("%d\n",n-ans/2);

	}

}

巴特西

POJ 1466 Girls and Boys (ZOJ 1137 )最大独立点集

最新文章

热门文章