【HDOJ 1068】Girls and Boys
二分图最大独立集问题 原本想用最大独立集 = 补图的最大团来做。。结果超时 后来改用二分图最大独立集 = 顶点数 – 二分图最大匹配来做，，。vis数组没用好 又超 最后改来改去改对了……
由于输入建图是双向的 所以要减两倍的最大匹配
代码如下:
;vector <int> head[555];bool vis[555];int link[555],n;bool can(int p){int i,v;for(i = 0; i < head[p].size(); ++i){v = head[p][i];if(!vis[v]){vis[v] = true;//！！递归之后不要变回false 否则之后会多次遍历 作无用的运算if(link[v] == -1 || can(link[v])){link[v] = p;return 1;}}}return 0;}int main(){int m,i,j,u,v,cnt;while(~scanf(“%d”,&n)){for(i = 0; i < n; ++i) head[i].clear();cnt = 0;for(i = 0; i < n; ++i){scanf(“%d: (%d)”,&u,&m);while(m–){scanf(“%d”,&v);head[u].push_back(v);}}memset(link,-1,sizeof(link));for(i = 0; i < n; ++i){memset(vis,0,sizeof(vis));if(can(i)) cnt++;}printf(“%d\n”,n – cnt/2);}return 0;}
在爱情里，有时候简单的一句话，能胜过千言万语。
