POJ 1466 最大独立点集

思路：匈牙利 n-ans/2;

// by SiriusRen
#include <cstdio>
#include <cstring>
#define N 505
using namespace std;
int jy,xx,yy,n,tot,ans;
int first[N],next[N*N],v[N*N],mat[N];
bool vis[N];
void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}
bool dfs(int x){
    for(int i=first[x];~i;i=next[i])
        if(!vis[v[i]]&&(vis[v[i]]=1)&&(!mat[v[i]]||dfs(mat[v[i]])))
                {mat[v[i]]=x;return 1;}
    return 0;
}
int main(){
    while(~scanf("%d",&n)){
        memset(first,-1,sizeof(first));
        memset(mat,0,sizeof(mat));
        ans=tot=0;xx=-1;
        while(xx!=n-1){
            scanf("%d: (%d)",&xx,&jy);
            while(jy--)scanf("%d",&yy),add(xx,yy);
        }
        for(int i=0;i<n;i++){memset(vis,0,sizeof(vis));ans+=dfs(i);}
        printf("%d
",n-ans/2);
    }
}