/*
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=71805#problem/C
*/
性质：
【1】二分图最大点独立数=顶点数-二分图的最大匹配
【2】二分图最小点覆盖数=二分图的最大匹配
这个题目就是求最大点独立集，根据性质【1】可以求解。
对于这个问题，我们可以根据性别的不同建立二分图，每两个可能Make Love的人连一条边，o(n*n)的效率可以建图。
然后跑一遍二分图的最大匹配，答案就出来了。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int MAXN=505; int nx,ny; int g[MAXN][MAXN]; int cx[MAXN],cy[MAXN]; int mk[MAXN]; int n; struct People { int age; char sex[5]; char music[105]; char sport[105]; }F[MAXN],M[MAXN]; int path(int u) { for(int v=0;v<ny;v++) { if(g[u][v]&&!mk[v]) { mk[v]=1; if(cy[v]==-1||path(cy[v])) { cx[u]=v; cy[v]=u; return 1; } } } return 0; } int MaxMatch() { int res=0; memset(cx,-1,sizeof(cx)); memset(cy,-1,sizeof(cy)); for(int i=0;i<nx;i++) { if(cx[i]==-1) { memset(mk,0,sizeof(mk)); res=res+path(i); } } return res; } bool ok(People a, People b) { if(abs(a.age-b.age)<=40&&strcmp(a.music,b.music)==0&&strcmp(a.sport,b.sport)!=0) return 1; return 0; } int main() { int T,i,j; scanf("%d",&T); while(T--) { nx=0,ny=0; memset(g,0,sizeof(g)); scanf("%d",&n); //建立二分图 for(i=1;i<=n;i++) { int age; char sex[5]; char music[105]; char sport[105]; scanf("%d%s%s%s",&age,sex,music,sport); if(sex[0]=='M') { M[nx].age=age; strcpy(M[nx].sex,sex); strcpy(M[nx].music,music); strcpy(M[nx].sport,sport); nx++; } else if(sex[0]=='F') { F[ny].age=age; strcpy(F[ny].sex,sex); strcpy(F[ny].music,music); strcpy(F[ny].sport,sport); ny++; } } for(i=0;i<nx;i++) for(j=0;j<ny;j++) if(ok(M[i],F[j])) g[i][j]=1; //跑二分图最大匹配， //二分图最大点独立数=顶点数-二分图的最大匹配 //二分图最小点覆盖数=二分图的最大匹配 printf("%d ",n-MaxMatch()); } return 0; }