首页 > 代码库 > poj 2771 Guardian of Decency 解题报告

poj 2771 Guardian of Decency 解题报告

2024-07-18 09:41:02   225人阅读

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

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

1、身高差距  > 40cm

2、相同性别

3、喜欢的音乐种类  不同

4、有共同喜爱的 运动

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

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

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

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

    

         

    

  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\n", 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 node14 {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", n-(maxmatch>>1));70         }71     }72     return 0;73 }

 


联系
我们