这是经典的最大点独立集
还是可以转化成最大匹配数，为什么呢，因为求出最大匹配数之和，匹配的边的两个端点互斥，只能去一个，所以最后结果就用总点数-最大匹配数即可
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int h[600],sex[600]; char music[600][200],ball[600][200]; int d[600][600],vis[600],lefts[600]; int n; bool match(int u) { for (int v=0;v<n;v++){ if (d[u][v] && !vis[v]){ vis[v]=1; if (lefts[v]==-1 || match(lefts[v])){ lefts[v]=u; return true; } } } return false; } int main() { int t; char tmp[3]; scanf("%d",&t); while (t--) { scanf("%d",&n); for (int i=0;i<n;i++){ scanf("%d%s%s%s",&h[i],tmp,music[i],ball[i]); if (tmp[0]==‘M‘) sex[i]=1; else sex[i]=0; } memset(d,0,sizeof d); for (int i=0;i<n;i++) for (int j=i+1;j<n;j++){ if (abs(h[i]-h[j])<=40 && (sex[i]^sex[j]) && strcmp(music[i],music[j])==0 && strcmp(ball[i],ball[j])!=0){ if (sex[i]==1) d[i][j]=1; else d[j][i]=1; } } int sum=0; memset(lefts,-1,sizeof lefts); for (int i=0;i<n;i++){ memset(vis,0,sizeof vis); if (match(i)) sum++; } int ans=n-sum; printf("%d\n",ans); } return 0; }
这个题目也可以不把男女生分开建图（上面我区分了男女，把男的放在左边） 全部统一建图，求出来的匹配数/2即可，原因很简单，其实就是统一建图就是把上面的图左右反过来又加在原图一下，所以匹配数是实际的两倍
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int h[600],sex[600]; char music[600][20],ball[600][200]; int d[600][600],vis[600],lefts[600]; int n; bool match(int u) { for (int v=0;v<n;v++){ if (d[u][v] && !vis[v]){ vis[v]=1; if (lefts[v]==-1 || match(lefts[v])){ lefts[v]=u; return true; } } } return false; } int main() { int t; char tmp[3]; scanf("%d",&t); while (t--) { scanf("%d",&n); for (int i=0;i<n;i++){ scanf("%d%s%s%s",&h[i],tmp,music[i],ball[i]); if (tmp[0]==‘M‘) sex[i]=1; else sex[i]=0; } memset(d,0,sizeof d); for (int i=0;i<n;i++) for (int j=i+1;j<n;j++){ if (abs(h[i]-h[j])<=40 && (sex[i]^sex[j]) && strcmp(music[i],music[j])==0 && strcmp(ball[i],ball[j])!=0){ d[i][j]=d[j][i]=1; // cout<<h[i]<<" "<<h[j]<<endl; // cout<<i<<" is connect "<<j<<endl; } else d[i][j]=d[j][i]=0; } int sum=0; memset(lefts,-1,sizeof lefts); for (int i=0;i<n;i++){ memset(vis,0,sizeof vis); if (match(i)) sum++; } //cout<<sum<<endl; int ans=n-sum/2; printf("%d\n",ans); } return 0; }
POJ 2771 最大点独立集,布布扣,bubuko.com
原文：http://www.cnblogs.com/kkrisen/p/3768766.html