二分图的最大独立点集,在构图的时候因为复制了一遍,所以求出来的最大匹配其实是两倍。
code:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 1010; int n; bool graph[MAXN][MAXN]; bool vis[MAXN]; int link[MAXN]; int find(int x) { int y; for(y=0;y<n;y++) { if(graph[x][y] && !vis[y]) { vis[y]=true; if(link[y]==-1 || find(link[y])) { link[y]=x; return true; } } } return false; } int main() { int i,j,a,m,tmp,ans; while(~scanf("%d",&n)) { ans=0; memset(link,-1,sizeof(link)); memset(graph,0,sizeof(graph)); for(i=0;i<n;i++) { scanf("%d: (%d) ",&a,&m); while(m--) { scanf("%d",&tmp); graph[a][tmp]=graph[tmp][a]=1; } } // for(i=0;i<n;i++) // { // for(j=0;j<n;j++) // { // printf("%d ",graph[i][j]); // } // puts(""); // } for(i=0;i<n;i++) { memset(vis,0,sizeof(vis)); if(find(i)) ans++; } printf("%d\n",n-ans/2); } return 0; }