POJ 1466 Girls and Boys(最大独立点集)
题意：有n个学生，其中他们之间某些人有联系，问你最多能找出多少个学生组成一个集合，使得这个集合内的学生任何两个之间没有联系。
思路：最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - 最大匹配数/2，然后就是匈牙利算法实现了。
> 这个问题拆点后的二分图为男在一边，女的在另一边。因此如果确定为一边的点，就不可能于同一边的点相连。而且由于在寻找最大匹配时不是枚举其中一边的点，而是枚举两边的所有点，所以得到的ans为最大匹配数 的两倍，因为每条匹配的边都算了两遍。
代码：
#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;}
