poj 2771 Guardian of Decency 解题报告

题目链接：

题目意思：有一个保守的老师要带他的学生来一次短途旅行，但是他又害怕有些人会变成情侣关系，于是就想出了一个方法：

1、身高差距 > 40cm

2、相同性别

3、喜欢的音乐种类 不同

4、有共同喜爱的 运动

只要满足其中这4个条件中的一个（当然越多越好啦），就可以将他们编为一组啦（一组两个人），求能被编为一组的最多组数。

这题实质上求的是二分图的最大独立集。 最大独立集 = 顶点数 - 最大匹配数

可以这样转化：两个人至少满足其中一个条件，那么就把四个条件都不满足的人连边（即配对），然后找出匹配数（也就是公式中的 最大匹配数），总人数减去，也就是答案。

lrj 版本（虽然有点长，不过代码很靓，美的享受，有赏心悦目之感）

  1 #include 
  2 #include 
  3 #include 
  4 #include <string>
  5 #include 
  6 #include 
  7 #include 
  8 
  9 using namespace std;
 10 
 11 const int maxn = 500 + 5;
 12 
 13 struct BPM
 14 {
 15     int n, m;
 16     int G[maxn][maxn];
 17     int left[maxn];
 18     bool T[maxn];
 19 
 20     void init(int n, int m)
 21     {
 22         this->n = n;
 23         this->m = m;
 24         memset(G, 0, sizeof(G));
 25     }
 26 
 27     bool match(int u)
 28     {
 29         for (int v = 0; v < m; v++)
 30         {
 31             if (G[u][v] && !T[v])
 32             {
 33                 T[v] = true;
 34                 if (left[v] == -1 || match(left[v]))
 35                 {
 36                     left[v] = u;
 37                     return true;
 38                 }
 39             }
 40         }
 41         return false;
 42     }
 43 
 44     int solve()
 45     {
 46         memset(left, -1, sizeof(left));
 47         int ans = 0;
 48         for (int u = 0; u < n; u++)
 49         {
 50             memset(T, 0, sizeof(T));
 51             if (match(u))
 52                 ans++;
 53         }
 54         return ans;
 55     }
 56 };
 57 
 58 BPM solver;
 59 
 60 struct Student
 61 {
 62     int h;
 63     string music, sport;
 64     Student(int h, string music, string sport): h(h), music(music), sport(sport){}
 65 };
 66 
 67 bool conflict(const Student& a, const Student& b)
 68 {
 69     return (abs(a.h-b.h) <= 40 && a.music == b.music && a.sport != b.sport);
 70 }
 71 
 72 int main()
 73 {
 74     int T, n;
 75     while (scanf("%d", &T) != EOF)
 76     {
 77         while (T--)
 78         {
 79             scanf("%d", &n);
 80             vector male, female;
 81             for (int i = 0; i < n; i++)
 82             {
 83                 int h;
 84                 string gender, music, sport;
 85                 cin >> h >> gender >> music >> sport;
 86                 if (gender[0] == 'M')
 87                     male.push_back(Student(h, music, sport));
 88                 else
 89                     female.push_back(Student(h, music, sport));
 90             }
 91             int x = male.size();
 92             int y = female.size();
 93             solver.init(x, y);
 94             for (int i = 0; i < x; i++)
 95             {
 96                 for (int j = 0; j < y; j++)
 97                 {
 98                     if (conflict(male[i], female[j]))
 99                         solver.G[i][j] = 1;
100                 }
101             }
102             printf("%d\n", x + y - solver.solve());
103         }
104     }
105     return 0;
106 }

这个是我的 （时间真心不敢恭维啊 [>_