POJ 1466 Girls and Boys

二分圖

//============================================================================

// Name        : hello.cpp

// Author      : key

// Version     : ∞

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <queue>

#include <stack>

#include <string>

#include <algorithm>

using namespace std;

#define NUM_INF 0x7FFFFFFF

const int MAXN = 505;

int n;

bool g[MAXN][MAXN];

int xm[MAXN];

int ym[MAXN];

bool chk[MAXN];

bool dfs(int u)

{

    int v;

    for(v=0;v<n;v++)

    {

        if(g[u][v] && !chk[v])

        {

            chk[v] = true;

            if(ym[v] == -1 || dfs(ym[v]))

            {

                ym[v] = u;

                xm[u] = v;

                return true;

            }

        }

    }

    return false;

}

int MaxMatch()

{

    int  u,ret=0;

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

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

    for(u=0;u<n;u++)

    {

        if(xm[u] == -1)

        {

            memset(chk,false,sizeof(chk));

            if(dfs(u))

                ret++;

        }

    }

    return ret;

}

int main()

{

    int i,u,v,num;

    while(scanf("%d",&n)!=EOF)

    {

        memset(g,false,sizeof(g));

        for(i=0;i<n;i++)

        {

            scanf("%d: (%d) ",&u,&num);

            while(num--)

            {

                scanf("%d",&v);

                g[u][v]=true;

            }

        }

        printf("%d\n",n-(MaxMatch()/2));

    }

    return 0;

}