pku1466 Girls and Boys

时间：2010-08-06 来源：Z_Q_2010

最大独立集的问题描述如下：给定无向图G(V,E)，其中AÍV，且EÇ{(i,j)½i,jÎA}=Æ，求A，使得½A½最大。一般地，我们都把最大独立集转化为最小覆盖集，然后根据逻辑运算定律求解

令B=V－A，则BÍV，且对于任意一条边(i,j)ÎE，有iÎB或jÎB，所以B是图G(V,E)的最小覆盖集。在这个转化过程中就用到了点的“补集转化”——用点集V减去求解目标集合A，以得到新的目标集合B。

#include<stdio.h>

const int Maxn=501;
bool g[Maxn][Maxn],visit[Maxn];
int link[Maxn];
int n;

bool find(int x)
{
    for(int i=0;i<n;i++)
    {
        if(g[x][i]&&!visit[i])
        {
            visit[i]=true;
            if(link[i]==-1||find(link[i]))
            {
                link[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{

    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                g[i][j]=false;

        for(int i=0;i<n;i++)
        {
            int num,k;
            scanf("%*d: (%d)",&num);
            for(int j=0;j<num;j++)
            {
                scanf("%d",&k);
                g[i][k]=true;
            }
        }

        int match=0;
        for(int i=0;i<n;i++)
            link[i]=-1;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                visit[j]=false;
            if(find(i))    match++;
        }

        printf("%d\n",n-match/2);
    }
    return 0;
}