Girls and Boys

本文主要是介绍Girls and Boys，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1068

这题大概意思就是说找出一个最大的集合使得该集合的任意两个人木有关系。

根据最大独立集 =顶点数 - 最大匹配数

由于题目没有给出哪些是男的哪些是女的，也就是说没有明显的二分图，所以将一个人拆成两个人进行最大匹配。由于一个拆成两个，所以最大匹配数应该是求出来的数除以2 。最后再用顶点数减就行了。

用邻接表，上代码

#include<iostream>

#include<cstdio>
#include<cstring>
using namespace std;
int n,map[1010][1010],vis[1010],link[1010];
int find(int a)
{
for(int i=0;i<n;i++)
{
if(!vis[i] && map[a][i])
{
vis[i]=1;
if(link[i]==-1 || find(link[i]))
{
link[i]=a;
return 1;
}
}
}
return 0;
}
int main()
{
while(cin>>n)
{
int stunum,num;
char mao,kong,left,right;
memset(map,0,sizeof(map));
memset(link,-1,sizeof(link));
for(int i=0;i<n;i++)
{
scanf("%d%c%c%c%d%c",&stunum,&mao,&kong,&left,&num,&right);
while(num--)
{
int temp;
scanf("%d",&temp);
map[i][temp]=1;
}
}
int count=0;
for(int i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
count+=find(i);
}
cout<<n-count/2<<endl;
}
return 0;
}

这篇关于Girls and Boys的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---