poj 2771 Guardian of Decency 解题报告

题目链接：http://poj.org/problem?id=2771

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

1、身高差距 > 40cm

2、相同性别

3、喜欢的音乐种类不同

4、有共同喜爱的运动

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

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

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

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

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <cmath>
  6 #include <vector>
  7 #include <algorithm>
  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<Student> 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
", x + y - solver.solve());
103         }
104     }
105     return 0;
106 }

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

之所以还要除以2，是因为男生(假设为 X 集合)跟女生的集合（Y）都是1~n，左右对称啦！

这样虽然不需要额外知道分别的男女生是多少，但是因为贪方便，时间也用多了，尤其对于 n 比较大的情况来说。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 const int maxn = 500 + 10;
 8 const int N = 100 + 10;
 9 int vis[maxn], match[maxn];
10 int map[maxn][maxn];
11 int n, maxmatch;
12 
13 struct node
14 {
15     int h;
16     char sex;
17     char music[N];
18     char sport[N];
19 }student[maxn];
20 
21 int dfs(int x)
22 {
23     for (int i = 1; i <= n; i++)
24     {
25         if (!vis[i] && map[x][i])
26         {
27             vis[i] = 1;
28             if (!match[i] || dfs(match[i]))
29             {
30                 match[i] = x;
31                 return 1;
32             }
33         }
34     }
35     return 0;
36 }
37 
38 void Hungary()
39 {
40     maxmatch = 0;
41     for (int i = 1; i <= n; i++)
42     {
43         memset(vis, 0, sizeof(vis));
44         maxmatch += dfs(i);
45     }
46 }
47 
48 int main()
49 {
50     int T;
51     while (scanf("%d", &T) != EOF)
52     {
53         while (T--)
54         {
55             scanf("%d", &n);
56             for (int i = 1; i <= n; i++)
57                 cin >> student[i].h >> student[i].sex >> student[i].music >> student[i].sport;
58             memset(map, 0, sizeof(map));
59             memset(match, 0, sizeof(match));
60             for (int i = 1; i <= n; i++)
61             {
62                 for (int j = i+1; j <= n; j++)
63                 {
64                     if (!(abs(student[i].h - student[j].h) > 40 || student[i].sex == student[j].sex || strcmp(student[i].music, student[j].music)|| !strcmp(student[i].sport, student[j].sport)))
65                         map[i][j] = map[j][i] = 1;
66                 }
67             }
68             Hungary();
69             printf("%d
", n-(maxmatch>>1));
70         }
71     }
72     return 0;
73 }