学步园

在一个二分图中,选择一些顶点,使得所有选择的顶点集合中没有任意两个顶点之间有边相连

方法：二分图匹配，可以证明，最大独立顶点集的数目就是总顶点数减去最大匹配数（也就是每个匹配有一个边扔掉）

(摘自：http://my.opera.com/IloveLunamaria/blog/show.dml/810972)

就是说：极小覆盖点集和极大独立点集互补

这题题我一直没看懂，所以一直纳闷为啥是  n-cnt/2  ，后来看懂题了，才知道原来这题的二部图两边集合的点都一样，所以相当于最大匹配求了两次，所以要减去 cnt 的一半，纠结了好久……

#include<stdio.h><br /> #include<string.h><br /> #define N 1001<br /> int n,map[N][N],match[N],vis[N];<br /> int dfs(int x)<br /> {<br /> int i;<br /> for(i=0;i<n;i++)<br /> {<br /> if(map[x][i] && !vis[i])<br /> {<br /> vis[i]=1;<br /> if(!match[i] || dfs(match[i]))<br /> {<br /> match[i]=x;<br /> return 1;<br /> }<br /> }<br /> }<br /> return 0;<br /> }<br /> int main()<br /> {<br /> int m,a,i,cnt,x;<br /> while(~scanf("%d",&n))<br /> {<br /> memset(map,0,sizeof(map));<br /> for(i=0;i<n;i++)<br /> {<br /> scanf("%d: (%d)",&x,&m);<br /> while(m--)<br /> {<br /> scanf("%d",&a);<br /> map[x][a]=1;<br /> }<br /> }<br /> memset(match,0,sizeof(match));<br /> for(cnt=0,i=0;i<n;i++)<br /> {<br /> memset(vis,0,sizeof(vis));<br /> if(dfs(i)) cnt++;<br /> }<br /> printf("%d/n",n-cnt/2);<br /> }<br /> return 0;<br /> }