POJ-1466-Girls and Boys(二分图-最大点独

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;
}