http://poj.org/problem?id=2771
Description
Input
Output
Sample Input
2 4 35 M classicism programming 0 M baroque skiing 43 M baroque chess 30 F baroque soccer 8 27 M romance programming 194 F baroque programming 67 M baroque ping-pong 51 M classicism programming 80 M classicism Paintball 35 M baroque ping-pong 39 F romance ping-pong 110 M romance Paintball
Sample Output
3 7
/**
poj 2771 最大独立集
题目大意：一个老师要带一部分人，要求所带的人中不能有可能出现会搞对象的（不满足题目中的条件之一则有可能），
问最多能带多少学生。
解题思路：所有可能搞对象的人匹配。求二分图的最大独立集就行。最大独立集=n-匹配数
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
const int maxn=505;
int n,high[maxn];
char mus[maxn][102],sex[maxn][2],spo[maxn][103];
int w[maxn][maxn];
int linker[maxn];
bool used[maxn];
bool dfs(int u)
{
int v;
for(v=0;v<n;v++)
{
if(w[u][v]&&!used[v])
{
used[v]=true;
if(linker[v]==-1||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int res=0;
int u;
memset(linker,-1,sizeof(linker));
for(u=0;u<n;u++)
{
memset(used,0,sizeof(used));
if(dfs(u))res++;
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%s%s%s",&high[i],sex[i],mus[i],spo[i]);
}
memset(w,0,sizeof(w));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(abs(high[i]-high[j])<=40&&strcmp(sex[i],sex[j])!=0&&strcmp(mus[i],mus[j])==0&&strcmp(spo[i],spo[j])!=0)
{
w[i][j]=w[j][i]=1;
}
}
}
printf("%d\n",n-hungary()/2);
}
return 0;
}
原文：http://blog.csdn.net/lvshubao1314/article/details/44177277