首页 > 代码库 > Girls and Boys(poj 1466)
Girls and Boys(poj 1466)
题目描述:
给出一系列男女配对意愿信息。求一个集合中的最大人数,满足这个集合中两两的人不能配对。
/* 二分图的最大独立集 因为没有给出具体的男生和女生,所以可以将数据扩大一倍,即n个男生,n个女生, 根据定理,最大独立集=总数-匹配数(本题应该除以2) */ #include<cstdio> #include<iostream> #include<cstring> #define N 510 using namespace std; int a[N][N],used[N],belong[N],n; bool find(int i) { for(int j=1;j<=n;j++) if(a[i][j]&&!used[j]) { used[j]=1; if(!belong[j]||find(belong[j])) { belong[j]=i; return true; } } return false; } void work() { for(int i=1;i<=n;i++) { int x,m;scanf("%d: (%d)",&x,&m);x++; for(int j=1;j<=m;j++) { int y;scanf("%d",&y);y++; a[x][y]=a[y][x]=1; } } int tot=0; for(int i=1;i<=n;i++) { memset(used,0,sizeof(used)); if(find(i))tot++; } printf("%d\n",n-tot/2); } int main() { while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); memset(belong,0,sizeof(belong)); work(); } return 0; }
Girls and Boys(poj 1466)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。