http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=137
http://poj.org/problem?id=1466
题目大意:
n个学生,他们中有的有关系,有的没有关系,求最多可以取出几个人,使得他们之间没有关系。
思路:
复制别人的。。。。。
最大独立集问题:在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值.如果图G满足二分图条件,则可以用二分图匹配来做.最大独立集点数 = 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 )最大独立点集
原文:http://blog.csdn.net/murmured/article/details/19301409