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 = 500 + 5;

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, 0, sizeof(G));
    }

    bool match(int u)
    {
        for (int v = 0; v < m; v++)
        {
            if (G[u][v] && !T[v])
            {
                T[v] = true;
                if (left[v] == -1 || match(left[v]))
                {
                    left[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    int solve()
    {
        memset(left, -1, sizeof(left));
        int ans = 0;
        for (int u = 0; u < n; u++)
        {
            memset(T, 0, 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) <= 40 && 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 = 0; i < n; i++)
            {
                int h;
                string gender, music, sport;
                cin >> h >> gender >> music >> sport;
                if (gender[0] == '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 = 0; i < x; i++)
            {
                for (int j = 0; j < y; j++)
                {
                    if (conflict(male[i], female[j]))
                        solver.G[i][j] = 1;
                }
            }
            printf("%d\n", x + y - solver.solve());
        }
    }
    return 0;
}

 

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

    

   

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

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

  

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int maxn = 500 + 10;
const int N = 100 + 10;
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 = 1; i <= n; i++)
    {
        if (!vis[i] && map[x][i])
        {
            vis[i] = 1;
            if (!match[i] || dfs(match[i]))
            {
                match[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

void Hungary()
{
    maxmatch = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        maxmatch += dfs(i);
    }
}

int main()
{
    int T;
    while (scanf("%d", &T) != EOF)
    {
        while (T--)
        {
            scanf("%d", &n);
            for (int i = 1; i <= n; i++)
                cin >> student[i].h >> student[i].sex >> student[i].music >> student[i].sport;
            memset(map, 0, sizeof(map));
            memset(match, 0, sizeof(match));
            for (int i = 1; i <= n; i++)
            {
                for (int j = i+1; j <= n; j++)
                {
                    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)))
                        map[i][j] = map[j][i] = 1;
                }
            }
            Hungary();
            printf("%d\n", n-(maxmatch>>1));
        }
    }
    return 0;
}