学步园

hdu 1068 Girls and Boys (最大匹配入门)

结论是：最大独立团=定点数-最大匹配

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#define ll __int64
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define new_edge(a,b,c) edge[tot].t = b , edge[tot].v = c , edge[tot].next = head[a] , head[a] = tot ++
using namespace std;

const int maxn = 501 ;
int cx[maxn] , cy[maxn] , nx , ny , n ;
int px[maxn] , py[maxn] ;
int vis[maxn] ;
vector<int> vec[maxn] ;

void build ( int u , int p ) {
    if ( !p ) px[++nx] = u ;
    else py[++ny] = u ;
    vis[u] = 1 ;
    vector<int>::iterator it ;
    for ( it = vec[u].begin () ; it != vec[u].end () ; it ++ ) {
        int v = *it ;
        if ( !vis[v] )
            build ( v , p ^ 1 ) ;
    }
}

int dfs ( int u ) {
    vector<int>::iterator it ;
    for ( it = vec[u].begin () ; it != vec[u].end () ; it ++ ) {
        int v = *it ;
        if ( !vis[v] ) {
            vis[v] = 1 ;
            if ( cy[v] == -1 || dfs ( cy[v] ) ) {
                cy[v] = u ;
                return 1 ;
            }
        }
    }
    return 0 ;
}

int main() {
    int i , j , k ;
    while ( scanf ( "%d" , &n ) != EOF ) {
        memset ( vis , 0 , sizeof ( vis ) ) ;
        for ( i = 0 ; i < n ; i ++ ) vec[i].clear () ;
        for ( i = 0 ; i < n ; i ++ ) {
            int a , b , c ;
            scanf ( "%d: (%d) " , &a , &b ) ;
            for ( j = 1 ; j <= b ; j ++ ) {
                scanf ( "%d" , &c ) ;
                vec[a].push_back ( c ) ;
            }
        }
        nx = ny = 0 ;
        for ( i = 0 ; i < n ; i ++ )
            if ( !vis[i] ) build ( i , 0 ) ;
        memset ( cy , -1 , sizeof ( cy ) ) ;
        int ans = 0 ;
        for ( i = 1 ; i <= nx ; i ++ ) {
            memset ( vis , 0 , sizeof ( vis ) ) ;
            ans += dfs ( px[i] ) ;
        }
        printf ( "%d\n" , n - ans ) ;
    }
    return 0;
}

/*
6
0: (1) 3
1: (1) 2
2: (2) 1 5
3: (2) 0 4
4: (2) 3 5
5: (2) 2 4
*/