http://poj.org/problem?id=2771
题意：
一个老师想带几个同学出去，但是他怕他们会谈恋爱，所以带出去的同学两两之间必须满足如下条件之一：
①身高差大于40 ②同性 ③喜欢的音乐风格不同 ④喜欢的运动相同
思路：
每两个人之间进行判断，如果不满足上面4个之一，则连一条线，说明他们是不能同时带出去的。然后找一个最大匹配，说明这几对中每队只能带出去一人，这样答案就很明显了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std; const int maxn=+; int n; struct node
{
int height;
char sex;
char music[];
char sport[];
}a[maxn]; int g[maxn][maxn];
int vis[maxn];
int match[maxn]; bool judge(int i,int j)
{
if(abs(a[i].height-a[j].height)> || a[i].sex == a[j].sex || strcmp(a[i].music,a[j].music)||!strcmp(a[i].sport,a[j].sport)) return true;
return false;
} bool dfs(int x)
{
for(int i=;i<n;i++)
{
if(!vis[i] && g[x][i])
{
vis[i]=;
if(match[i]==- || dfs(match[i]))
{
match[i]=x;
return true;
}
}
}
return false;
} int main()
{
//freopen("D:\\txt.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
memset(g,,sizeof(g));
scanf("%d",&n);
for(int i=;i<n;i++)
{
cin>>a[i].height>>a[i].sex>>a[i].music>>a[i].sport;
}
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{ if(i==j) continue;
if(!judge(i,j)) g[i][j]=;
}
int ans=;
memset(match,-,sizeof(match));
for(int i=;i<n;i++)
{
memset(vis,,sizeof(vis));
{
if(dfs(i)) ans++;
}
}
cout<<n-ans/<<endl;
}
}