POJ 1466 Girls and Boys (ZOJ 1137 )最大独立点集 - c++编程基础

题目大意：

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

思路：

复制别人的。。。。。

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

#include
  
   
#include
   
     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