题目链接：
题目意思：有一个保守的老师要带他的学生来一次短途旅行，但是他又害怕有些人会变成情侣关系，于是就想出了一个方法：
1、身高差距 > 40cm
2、相同性别
3、喜欢的音乐种类 不同
4、有共同喜爱的 运动
只要满足其中这4个条件中的一个（当然越多越好啦），就可以将他们编为一组啦（一组两个人），求能被编为一组的最多组数 。
【poj2771 Guardian of Decency解题报告】这题实质上求的是二分图的最大独立集 。最大独立集 = 顶点数 - 最大匹配数
可以这样转化：两个人至少满足其中一个条件 ， 那么就把四个条件都不满足的人连边（即配对），然后找出匹配数（也就是公式中的 最大匹配数），总人数减去，也就是答案 。
lrj 版本（虽然有点长 ， 不过代码很靓，美的享受 ， 有赏心悦目之感）
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include89 using namespace std; 1011 const int maxn = 500 + 5; 1213 struct BPM 14 { 15int n, m; 16int G[maxn][maxn]; 17int left[maxn]; 18bool T[maxn]; 1920void init(int n, int m) 21{ 22this->n = n; 23this->m = m; 24memset(G, 0, sizeof(G)); 25} 2627bool match(int u) 28{ 29for (int v = 0; v < m; v++) 30{ 31if (G[u][v] && !T[v]) 32{ 33T[v] = true; 34if (left[v] == -1 || match(left[v])) 35{ 36left[v] = u; 37return true; 38} 39} 40} 41return false; 42} 4344int solve() 45{ 46memset(left, -1, sizeof(left)); 47int ans = 0; 48for (int u = 0; u < n; u++) 49{ 50memset(T, 0, sizeof(T)); 51if (match(u)) 52ans++; 53} 54return ans; 55} 56 }; 5758 BPM solver; 5960 struct Student 61 { 62int h; 63string music, sport; 64Student(int h, string music, string sport): h(h), music(music), sport(sport){} 65 }; 6667 bool conflict(const Student& a, const Student& b) 68 { 69return (abs(a.h-b.h) <= 40 && a.music == b.music && a.sport != b.sport); 70 } 7172 int main() 73 { 74int T, n; 75while (scanf("%d", &T) != EOF) 76{ 77while (T--) 78{ 79scanf("%d", &n); 80vector male, female; 81for (int i = 0; i < n; i++) 82{ 83int h; 84string gender, music, sport; 85cin >> h >> gender >> music >> sport; 86if (gender[0] == 'M') 87male.push_back(Student(h, music, sport)); 88else 89female.push_back(Student(h, music, sport)); 90} 91int x = male.size(); 92int y = female.size(); 93solver.init(x, y); 94for (int i = 0; i < x; i++) 95{ 96for (int j = 0; j < y; j++) 97{ 98if (conflict(male[i], female[j])) 99solver.G[i][j] = 1;100}101}102printf("%d\n", x + y - solver.solve());103}104}105return 0;106 }
这个是我的 （时间真心不敢恭维啊 [>_
