HDU 1068 ：题目链接

题意：一些男孩和女孩，给出一些人物关系，然后问能找到最多有多少个人都互不认识。

转换一下：就是大家都不认识的人，即最大独立集合

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <math.h>

#define init(a) memset(a,0,sizeof(a))

#define PI acos(-1,0)

using namespace std;

const int maxn = 510;

const int maxm = 100001;

#define lson left, m, id<<1

#define rson m+1, right, id<<1|1

#define min(a,b) (a>b)?b:a

#define max(a,b) (a>b)?a:b

const int N = 50010;

int ma[maxn][maxn];

int line[maxn];

bool vis[maxn];

int k,n,m;

int DFS(int u)

{

   // printf("u = %d\n",u);

    for(int v = 0;v<k;v++)

    {

        if(ma[u][v]== 1 && vis[v]==0)

        {

            vis[v] = 1;

            if(line[v]== -1 || DFS(line[v]))

            {

                line[v] = u;

                return 1;

            }

        }

    }

    return 0;

}

int K_M()

{

    int ans = 0;

    memset(line,-1,sizeof(line));

    for(int i = 0;i<k;i++)

    {

        init(vis);

       ans += DFS(i);

    }

    return ans;

}

int main()

{

    int x,y;

    while(~scanf("%d",&k))

    {

        init(ma);

        for(int j = 1;j<=k;j++)

        {

        scanf("%d: (%d)",&m,&n);

        for(int i = 1;i<=n;i++)

        {

            scanf("%d",&x);

            ma[m][x] = 1;

        }

        }

//最大独立集合 = 顶点数 - 最大匹配数

        int ans = K_M();

        ans /= 2;

        printf("%d\n",k-ans);

    }

    return 0;

}