HDU 1068 Girls and Boys（最大独立集）

[cpp] 
/*
题意：n个同学，一些男女同学会有缘分成为情侣，格式ni:(m) n1 n2 n3表示同学ni有缘与n1,n2,n3成为情侣，求集合中不存在有缘成为情侣的同学的最大同学数。
题解：
独立集：图的顶点集的子集，其中任意两点不相邻
最大独立集 = 顶点数 - 最大匹配数
由于本题是从整个点集搜索，并不是将点集分开成（A）（B)，（1->2）(2->1)对称存在，所以相当于搜索了两遍。因此真正最大匹配数等于最大匹配数/2.
具体我也不明白其中的原理，只是理解。
*/ 
 
#include <iostream> 
using namespace std; 
 
const int nMax = 500; 
int n; 
int map[nMax][nMax]; 
int link[nMax]; 
int useif[nMax]; 
 
bool can(int t) 
{ 
    for(int i = 0; i < n; ++ i) 
    { 
        if(!useif[i] && map[t][i]) 
        { 
            useif[i] = 1; 
            if(link[i] == -1 || can(link[i])) 
            { 
                link[i] = t; 
                return 1; 
            } 
        } 
    } 
    return 0; 
} 
 
int main() 
{ 
    //freopen("f://data.in", "r", stdin); 
    while(scanf("%d", &n) != EOF) 
    { 
        memset(map, 0, sizeof(map)); 
        memset(link, -1, sizeof(link)); 
        int u, k, v; 
        for(int i = 0; i < n; ++ i) 
        { 
            scanf("%d: (%d)", &u, &k); 
            while(k --) 
            { 
                scanf("%d", &v); 
                map[u][v] = 1; 
            }  www.zzzyk.com
        } 
        int num = 0; 
        for(int i = 0; i < n; ++ i) 
        { 
            memset(useif, 0, sizeof(useif)); 
            if(can(i)) ++ num; 
        } 
        printf("%d\n", n - num / 2); 
    } 
    return 0; 
} 
作者：lhshaoren

补充：软件开发 , C++ ,