Girls and Boys
题意：
- 找出尽量多的人，两者之间没有参加"romantically involved"
思路：
- 最大点独立集就是点集中的任何两点没有之间相连的边
最大点独立集==总点数-最大边匹配注意：图中的总点数是人数的两倍，因为每个人在建边的时候即在起点集合又在终点集合。这个存储关系时是双向的所以求出的最大匹配应该除以2
最大点独立集==(建图的总点数-建图的最大边匹配)/2
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>vep[550];
int n,m;
int vis[550];
int match[550];
void init(int n)
{
for(int i=0;i<n;i++)
{
vep[i].clear( );
match[i]=-1;
}
}
int Hungarian(int x)
{
for(int i=0;i<vep[x].size( );i++)
{
int v=vep[x][i];
if(!vis[v])
{
vis[v]=1;
if(match[v]==-1||Hungarian(match[v]))
{
match[v]=x;
return 1;
}
}
}
return 0;
}
int main( )
{
while(~scanf("%d",&n))
{
init(n);
int x,y;
char c;
for(int i=0;i<n;i++)
{
scanf("%d%c%c%c%d%c",&x,&c,&c,&c,&m,&c);
for(int i=1;i<=m;i++)
{
scanf("%d",&y);
vep[x].push_back(y);
}
}
int ans=0;
for(int i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
if(Hungarian(i))
{
ans++;
}
}
printf("%d\n",n-ans/2);
}
return 0;
}
