这个算是经典题了。
郁闷啊，怎么最大独立集都是拿学生不准谈恋爱作为背景。。
将可以谈的童鞋之间连线，求最大匹配，然后用总顶点数 - 最大匹配数即可。
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> #define MAX 505 using namespace std; typedef struct NODE{ int h; char sex,mus[20],hob[20]; }NODE; NODE p[MAX]; int used[MAX],match[MAX]; int map[MAX][MAX]; int Augement(int n,int x) { int i ; for(i=1; i<=n; i++) if( map[x][i] && !used[i] ) { used[i] = 1; if( !match[i] || Augement(n,match[i]) ) { match[i] = x; return 1; } } return 0; } int Hungary(int n) { int i,sum = 0; memset(match,0,sizeof(match)); for(i=1; i<=n; i++) { memset(used,0,sizeof(used)); if( Augement(n,i) ) sum++; } return sum; } int love(int i,int k) { if( abs(p[i].h - p[k].h) > 40 ) return 0; if( p[i].sex == p[k].sex ) return 0; if( strcmp(p[i].mus,p[k].mus) ) return 0; if( strcmp(p[i].hob,p[k].hob) == 0 ) return 0; return 1; } int main() { int ncases; int n,i,k; scanf("%d",&ncases); while( ncases-- ) { memset(map,0,sizeof(map)); scanf("%d",&n); for(i=1; i<=n; i++) scanf("%d %c %s %s",&p[i].h,&p[i].sex,p[i].mus,p[i].hob); for(i=1; i<=n; i++) for(k=1; k<=n; k++) if( love(i,k) ) map[i][k] = 1; int ans = Hungary(n); printf("%d/n",n-ans/2); } return 0; }
