Guardian of Decency·匹配问题·二分图问题

admin管理员组

文章数量:1658731

Guardian of Decency

• 题目信息
• • 输入
  • 输出
  • 测试用例
• 解答

题目信息

Frank N. Stein is a very conservative high-school teacher. He wants to take some of his students on an excursion, but he is afraid that some of them might become couples. While you can never exclude this possibility, he has made some rules that he thinks indicates a low probability two persons will become a couple:
Their height differs by more than 40 cm.
They are of the same sex.
Their preferred music style is different.
Their favourite sport is the same (they are likely to be fans of different teams and that would result in fighting).
So, for any two persons that he brings on the excursion, they must satisfy at least one of the requirements above. Help him find the maximum number of persons he can take, given their vital information.
弗兰克·斯坦因是一位非常保守的高中教师。他想带一些学生去远足，但他担心他们中的一些人可能会成为夫妇。虽然你永远不能排除这种可能性，但他制定了一些规则，他认为这表明两个人成为夫妻的可能性很低：
他们的身高相差超过40厘米。
他们是同性。
他们喜欢的音乐风格不同。
他们最喜欢的运动是相同的（他们可能是不同球队的球迷，这会导致打架）。
因此，对于他带来的任何两个人，他们必须至少满足上述一项要求。帮助他找到最大数量的人，他可以采取，鉴于他们的重要信息。

输入

The first line of the input consists of an integer T ≤ 100 giving the number of test cases. The first line of each test case consists of an integer N ≤ 500 giving the number of pupils. Next there will be one line for each pupil consisting of four space-separated data items:
an integer h giving the height in cm;
a character ‘F’ for female or ‘M’ for male;
a string describing the preferred music style;
a string with the name of the favourite sport.
No string in the input will contain more than 100 characters, nor will any string contain any whitespace.
输入的第一行由一个T≤100的整数组成，给出了测试用例的数量。每个测试用例的第一行由一个N≤500的整数组成，给出学生的数量。接下来，每个学生有一行，由四个空格分隔的数据项组成：
一个整数h，表示高度(cm);
“F”代表女性，“M”代表男性;
描述喜欢的音乐风格的弦;
带有最喜爱运动名称的字符串。
输入中的任何字符串都不能包含超过100个字符，也不能包含任何空格。

输出

For each test case in the input there should be one line with an integer giving the maximum number of eligible pupils.
对于输入中的每个测试用例，应该有一行整数，给出合格学生的最大数量。

测试用例

2
4
35 M classicism programming
0 M baroque skiing
43 M baroque chess
30 F baroque soccer
8
27 M romance programming
194 F baroque programming
67 M baroque ping-pong
51 M classicism programming
80 M classicism Paintball
35 M baroque ping-pong
39 F romance ping-pong
110 M romance Paintball

3
7

解答

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

struct People
{
    int height;
    char sex;
    char music[100];
    char sport[100];
} man[505], woman[505], temp;
int manNum, womanNum;
bool vis[505];
bool data[505][505];
int merg[505];//记录着伴侣是谁

///关系确定的判断
bool matching(People n, People m)
{
    if (abs(n.height - m.height) <= 40 && !strcmp(n.music, m.music) && strcmp(n.sport, m.sport))
    {//找到匹配的一对
        return true;
    }
    else
    {
        return false;
    }
}

//模板：二分匹配的模板
bool Find(int x)
{
    for (int i = 0; i < womanNum; i++)
    {//以每一个男性来遍历每一个女性
        if (data[x][i] && !vis[i])
        {//如果他们存在关系，且没有被遍历过
            vis[i] = true;

            //如果i没有伴侣，或者他的伴侣存在另外一条关系。则i是x的了。
            if (merg[i] == -1 || Find(merg[i]))
            {
                merg[i] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(data, 0, sizeof(data));
        manNum = womanNum = 0;
        memset(merg, -1, sizeof(merg));

        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> temp.height >> temp.sex >> temp.music >> temp.sport;
            if (temp.sex == 'M')
            {//男人
                woman[womanNum++] = temp;
            }
            else
            {//女人
                man[manNum++] = temp;
            }
        }

        //确定二者的关系,两两遍历
        for (int i = 0; i < manNum; i++)
        {
            for (int j = 0; j < womanNum; j++)
            {
                if (matching(man[i], woman[j]))
                {
                    data[i][j] = true;
                }
            }
        }

        int cnt = 0;
        for (int i = 0; i < manNum; i++)
        {//这里以男人视角来匹配女性
            memset(vis, 0, sizeof(vis));
            if (Find(i))
            {
                cnt++;
            }
        }
        //把存在关系的其中一个人删掉
        cout << n - cnt << endl;
    }
    return 0;
}

本文标签： GuardianDecency