URAL 1208. Legendary Teams Contest

Author: 2015-08-22

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1208

1208. Legendary Teams Contest

Time limit: 1.0 second
Memory limit: 64 MB
Nothing makes as old as years. A lot of cool contests are gone, a lot of programmers are not students anymore and are not allowed to take part at the contests. Though their spirit is fresh and young as it was years ago! And so once they decided to make a contest at the Ural State University among the veteran teams…
To make the contest interesting, they decided to invite as much “legendary” teams as possible. The jury has made a short list of teams, which have shown the best results in the old good times, thus being worthy to hold the name of “legendary”. All those teams were invited to take part of the contest, and all of them accepted the invitations. But they have forgotten one important thing at the jury: during the long history of the contests at the university, the teams happened to change and some programmers managed to contest in different “legendary” teams. Though, the jury decided not to give up the initial idea and to form as much legendary teams as possible to participate at the contest — and your program should help the jury!

Input

The first line contains a positive integer K, 1 ≤ K ≤ 18. It is the number of all the legendary teams. There follow the descriptions of the teams in K lines. Each of those lines contains three names of the team members of the respective team. All names are written with not more than 20 small Latin letters.

Output

You should output the maximal possible number of legendary teams of veterans, that could simultaneously participate at the contest.

Sample

input output 
7
gerostratos scorpio shamgshamg
zaitsev silverberg cousteau
zaitsev petersen shamgshamg
clipper petersen shamgshamg
clipper bakirelli vasiliadi
silverberg atn dolly
knuth dijkstra bellman
 
4
Problem Author: Leonid Volkov
Problem Source: USU Internal Contest, March 2002

2. 思路

给出若干个候选参赛队伍，同一个人可能会在多个队伍中出现。求能同时参赛的最多队伍数。

队伍最多只有18个，使用DFS穷举。如果队伍中的三个人都处于可选状态，则选择这个队伍，并把三个人全部标记为不可选，队伍计数加1，保存整个穷举过程中的最大队伍计数即可。

3. 代码

#include <stdio.h>
#include <iostream>
#include <string>
#include <map>
#include <vector>

#define MAX_TEAM_NUM 18

using namespace std;

struct TeamRecord;
typedef struct TeamRecord Team;
void solveE2g();
int inputTeamList(Team teams[], map<string, int> *isTeamedUp);
void printDict(map<string, int> m);
void findMaxTeamNum(int teamId, int teamNum, int totalNum);

struct TeamRecord {
    string member[3];
};

int main() {
    solveE2g();
    return 0;
}

Team teams[MAX_TEAM_NUM];
map<string, int> isTeamedUp;
int maxNum;
void solveE2g() {
    int k;

    k = inputTeamList(teams, &isTeamedUp);
    //printDict(isTeamedUp);

    for (int teamId = 0; teamId < k; ++teamId) {
        //printDict(isTeamedUp);
        isTeamedUp[teams[teamId].member[0]] = 1;
        isTeamedUp[teams[teamId].member[1]] = 1;
        isTeamedUp[teams[teamId].member[2]] = 1;
        findMaxTeamNum(teamId + 1, 1, k);
        isTeamedUp[teams[teamId].member[0]] = 0;
        isTeamedUp[teams[teamId].member[1]] = 0;
        isTeamedUp[teams[teamId].member[2]] = 0;
    }

    cout << maxNum << endl;
}

int inputTeamList(Team teams[], map<string, int> *isTeamedUp) {
    int k;

    scanf("%d\n", &k);
    for (int i = 0; i < k; ++i) {
        cin >> teams[i].member[0] >> teams[i].member[1] >> teams[i].member[2];
        for (int j = 0; j < 3; ++j) {
            if ((*isTeamedUp).count(teams[i].member[j]) == 0) {
                (*isTeamedUp)[teams[i].member[j]] = 0;
            }
        }
    }

    return k;
}

void findMaxTeamNum(int teamId, int teamNum, int totalNum) {
    //printDict(isTeamedUp);
    maxNum = maxNum > teamNum ? maxNum : teamNum;
    if (teamId < totalNum) {
        if (isTeamedUp[teams[teamId].member[0]] == 0 && isTeamedUp[teams[teamId].member[1]] == 0 && isTeamedUp[teams[teamId].member[2]] == 0) {
            isTeamedUp[teams[teamId].member[0]] = 1;
            isTeamedUp[teams[teamId].member[1]] = 1;
            isTeamedUp[teams[teamId].member[2]] = 1;
            findMaxTeamNum(teamId + 1, teamNum + 1, totalNum);
            isTeamedUp[teams[teamId].member[0]] = 0;
            isTeamedUp[teams[teamId].member[1]] = 0;
            isTeamedUp[teams[teamId].member[2]] = 0;

        } 
        findMaxTeamNum(teamId + 1, teamNum, totalNum);
    }
}


void printDict(map<string, int> m) {
    for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it) {
        cout << it->first << " " << it->second << "\n";
    }
    cout << endl;
}