POJ 1466 Girls and Boys(最大独立点集)

题意：有n个学生，其中他们之间某些人有联系，问你最多能找出多少个学生组成一个集合，使得这个集合内的学生任何两个之间没有联系。

思路：最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - 最大匹配数/2，然后就是匈牙利算法实现了。

> 这个问题拆点后的二分图为男在一边，女的在另一边。因此如果确定为一边的点，就不可能于同一边的点相连。而且由于在寻找最大匹配时不是枚举其中一边的点，而是枚举两边的所有点，所以得到的ans为最大匹配数 的两倍，因为每条匹配的边都算了两遍。
 
代码：
[cpp] 
<span style="font-size:18px;">#include <iostream> 
#include <algorithm> 
#include <cmath> 
using namespace std; 
const int MAXN=125; 
int uN,vN;   
int map[MAXN][MAXN]; 
int match[MAXN]; 
bool visit[MAXN];  
bool search(int u){ 
    int v; 
    for(v=1;v<=vN;v++) 
        if(map[u][v]&&!visit[v]){ 
            visit[v]=true; 
            if(match[v]==-1||search(match[v])){ 
                match[v]=u; 
                return true; 
            } 
        } 
    return false; 
} 
 
int hungary(){ 
    int res=0; 
    int u; 
    memset(match,-1,sizeof(match)); 
    for(u=1;u<=uN;u++){ 
        memset(visit,0,sizeof(visit)); 
        if(search(u))  res++; 
    } 
    return res; 
} 
long long a[1010]; 
 
int main(){ 
    int t; 
    int n; 
    int i, j,m,a,b; 
    scanf("%d", &t); 
    while(t --){ 
        scanf("%d%d", &n,&m); 
        memset(map, 0, sizeof(map)); 
        uN = n; 
        vN = n; 
        for(i = 0; i < m ; i ++){ 
             scanf("%d%d",&a,&b); 
             map[a][b]=1; 
        } 
        int ans = n - hungary(); 
        printf("%d/n", ans); 
    } 
    return 0; 
} 
</span>