Girls and Boys---hdu1068（最大独立集=顶点数-最大匹配）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1068

题意：有n个人，他们之间存在着恋爱关系，现在告诉你每个人和其他人的关系，然后要从这n个人间选出尽可能多的人组成一个集合，使得集合中的人之间不存在恋爱关系；

符合最大独立集的定义所以是顶点数-最大匹配

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#include<map>
using namespace std;
#define N 510
#define INF 0x3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))

int n, used[N], G[N][N], vis[N];

int Find(int u)
{
    for(int i=0; i<n; i++)
    {
        if(!vis[i] && G[u][i])
        {
            vis[i] = 1;
            if(!used[i] || Find(used[i]))
            {
                used[i] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        met(G, 0);
        for(int i=0; i<n; i++)
        {
            int u, v, k;
            scanf("%d: (%d)", &u, &k);
            for(int j=1; j<=k; j++)
            {
                scanf("%d", &v);
                G[u][v] = 1;
            }
        }
        int ans = 0;
        met(used, 0);
        for(int i=0; i<n; i++)///计算了两次，所以下面要除以2；
        {
            met(vis, 0);
            ans+=Find(i);
        }
        printf("%d
", n-ans/2);
    }
    return 0;
}