poj 2771 Guardian of Decency 解题报告

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

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

1、身高差距 > 40cm

2、相同性别

3、喜欢的音乐种类不同

4、有共同喜爱的运动

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

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

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

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

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 struct BPM

 {

     int n, m;

     int G[maxn][maxn];

     int left[maxn];

     bool T[maxn];

     void init(int n, int m)

     {

         this->n = n;

         this->m = m;

         memset(G, , sizeof(G));

     }

     bool match(int u)

     {

         for (int v = ; v < m; v++)

         {

             if (G[u][v] && !T[v])

             {

                 T[v] = true;

                 if (left[v] == - || match(left[v]))

                 {

                     left[v] = u;

                     return true;

                 }

             }

         }

         return false;

     }

     int solve()

     {

         memset(left, -, sizeof(left));

         int ans = ;

         for (int u = ; u < n; u++)

         {

             memset(T, , sizeof(T));

             if (match(u))

                 ans++;

         }

         return ans;

     }

 };

 BPM solver;

 struct Student

 {

     int h;

     string music, sport;

     Student(int h, string music, string sport): h(h), music(music), sport(sport){}

 };

 bool conflict(const Student& a, const Student& b)

 {

     return (abs(a.h-b.h) <=  && a.music == b.music && a.sport != b.sport);

 }

 int main()

 {

     int T, n;

     while (scanf("%d", &T) != EOF)

     {

         while (T--)

         {

             scanf("%d", &n);

             vector<Student> male, female;

             for (int i = ; i < n; i++)

             {

                 int h;

                 string gender, music, sport;

                 cin >> h >> gender >> music >> sport;

                 if (gender[] == 'M')

                     male.push_back(Student(h, music, sport));

                 else

                     female.push_back(Student(h, music, sport));

             }

             int x = male.size();

             int y = female.size();

             solver.init(x, y);

             for (int i = ; i < x; i++)

             {

                 for (int j = ; j < y; j++)

                 {

                     if (conflict(male[i], female[j]))

                         solver.G[i][j] = ;

                 }

             }

             printf("%d\n", x + y - solver.solve());

         }

     }

     return ;

 }

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

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

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

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int maxn =  + ;

 const int N =  + ;

 int vis[maxn], match[maxn];

 int map[maxn][maxn];

 int n, maxmatch;

 struct node

 {

     int h;

     char sex;

     char music[N];

     char sport[N];

 }student[maxn];

 int dfs(int x)

 {

     for (int i = ; i <= n; i++)

     {

         if (!vis[i] && map[x][i])

         {

             vis[i] = ;

             if (!match[i] || dfs(match[i]))

             {

                 match[i] = x;

                 return ;

             }

         }

     }

     return ;

 }

 void Hungary()

 {

     maxmatch = ;

     for (int i = ; i <= n; i++)

     {

         memset(vis, , sizeof(vis));

         maxmatch += dfs(i);

     }

 }

 int main()

 {

     int T;

     while (scanf("%d", &T) != EOF)

     {

         while (T--)

         {

             scanf("%d", &n);

             for (int i = ; i <= n; i++)

                 cin >> student[i].h >> student[i].sex >> student[i].music >> student[i].sport;

             memset(map, , sizeof(map));

             memset(match, , sizeof(match));

             for (int i = ; i <= n; i++)

             {

                 for (int j = i+; j <= n; j++)

                 {

                     if (!(abs(student[i].h - student[j].h) >  || student[i].sex == student[j].sex || strcmp(student[i].music, student[j].music)|| !strcmp(student[i].sport, student[j].sport)))

                         map[i][j] = map[j][i] = ;

                 }

             }

             Hungary();

             printf("%d\n", n-(maxmatch>>));

         }

     }

     return ;

 }

巴特西

poj 2771 Guardian of Decency 解题报告

最新文章

热门文章