来源http://acm.hdu.edu.cn/showproblem.php?pid=1068
最大独立集=节点数-最大匹配集
一开始用vector存储图，求其最大匹配数，一直wr，百思不得其解。
后面改成用二维数组存储就能ac了，很奇怪。又有什么忽略的吗？
#include<stdio.h> #include<math.h> #include<string> #include<vector> using namespace std; int flag[555]; int match[555]; int n; //vector<int> map[555]; int map[555][555]; bool dfs(int u) { for(int i=0;i<n;i++) { if(!flag[i]&&map[u][i]) { flag[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; //match[u]=map[u][i]; return true; } } } return false; } int hungary() { int res=0; memset(match,-1,sizeof(match)); for(int i=0;i<n;i++) { memset(flag,0,sizeof(flag)); if(dfs(i))res++; } return res; } int main() { int i,j,node,num,a; while(~scanf("%d",&n)) { memset(map,0,sizeof(map)); memset(flag,0,sizeof(flag)); for(i=0;i<n;i++) { scanf("%d: (%d)",&node,&num); while(num--) { scanf("%d",&a);map[node][a]=1;; } } printf("%d\n",n-hungary()/2);//无向图需除2 } return 0; }
