Time Limit: 5000MS | Memory Limit: 10000K | |
Total Submissions: 14701 | Accepted: 6613 |
Description
Input
Output
Sample Input
7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3 0: (2) 1 2 1: (1) 0 2: (1) 0
Sample Output
5 2
最大独立集=点数-最大匹配数
这道题目的cnt要除以2,因为没分二分图的两侧
代码
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int n,ma[505][505],link[505],vis[505]; int dfs(int x) { for(int i=1;i<=n;i++) { if(!vis[i] && ma[x][i]==1) { vis[i]=1; if(!link[i] || dfs(link[i])==1) { link[i]=x; return 1; } } } return 0; } int main() { freopen("a.in","r",stdin); while(scanf("%d",&n)!=EOF) { memset(ma,0,sizeof(ma)); memset(link,0,sizeof(link)); int k,x,y; for(int i=1;i<=n;i++) { scanf("%d: (%d)",&k,&x); k++; for(int j=1;j<=x;j++) { scanf("%d",&y); y++; ma[k][y]=1; } } int cnt=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) cnt++; } printf("%d\n",n-cnt/2); } return 0; }
【二分图最大独立集】poj 1466 Girls and Boys
原文:https://www.cnblogs.com/andylnx/p/14049462.html