Skip to content

L3-015 球队“食物链”

Statement

Metadata

  • 作者: 李文新
  • 单位: 北京大学
  • 代码长度限制: 16 KB
  • 时间限制: 2000 ms
  • 内存限制: 128 MB

某国的足球联赛中有N支参赛球队，编号从1至N。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。

联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个1至N的排列{ T_1 T_2 \cdots T_N }，满足：球队T_1战胜过球队T_2，球队T_2战胜过球队T_3，\cdots，球队T_{(N-1)}战胜过球队T_N，球队T_N战胜过球队T_1。

现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”，请找出字典序最小的。

注：排列{ a_1 a_2 \cdots a_N}在字典序上小于排列{ b_1 b_2 \cdots b_N }，当且仅当存在整数K（1 \le K \le N），满足：a_K < b_K且对于任意小于K的正整数i，a_i=b_i。

输入格式

输入第一行给出一个整数N（2 \le N \le 20），为参赛球队数。随后N行，每行N个字符，给出了N\times N的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：W表示球队i战胜球队j，L表示球队i负于球队j，D表示两队打平，-表示无效（当i=j时）。输入中无多余空格。

输出格式

按题目要求找到“食物链”T_1 T_2 \cdots T_N，将这N个数依次输出在一行上，数字间以1个空格分隔，行的首尾不得有多余空格。若不存在“食物链”，输出“No Solution”。

输入样例1 

5
-LWDW
W-LDW
WW-LW
DWW-W
DDLW-

输出样例1 

1 3 5 4 2

输入样例2 

5
-WDDW
D-DWL
DD-DW
DDW-D
DDDD-

输出样例2 

No Solution

Tutorial

思路：

  • 用一个数组标记 vis[i][j] 胜负
  • 遍历每一行
  • 如果 碰到 W 那么 vis[i][j] = 1
  • 如果 碰到 L 那么 vis[j][i] = 1
  • 然后食物链中所有队伍都有而且要保持字典序最小
  • 那么毫无疑问第一个必然是 1
  • 所以就从dfs(int cur, int step)
  • cur表示搜到第几支队伍step表示搜到第几步了
  • 如果剩下未标记的队伍 都没有战胜队伍1的那么就要剪去了
  • 因为再往下搜也是不能构成食物链的

Solution

#include <ctype.h>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double PI = 3.14159265358979323846264338327;
const double E = exp(1);
const double eps = 1e-6;

const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;

string s[25];
int vis[20][20];

map<int, int> m;

vector<int> v;

int ans, n;

void dfs(int cur, int step) {
    if (ans == 1)
        return;
    if (step == n && ans == -1) {
        if (vis[cur][0])
            ans = 1;
        return;
    } else {
        bool cut = false;
        for (int i = 0; i < n; i++) {
            if (m[i] == 0 && vis[i][0])
                cut = true;
        }
        if (cut == false)
            return;
        for (int i = 0; i < n && ans == -1; i++) {
            if (m[i] == 0 && vis[cur][i]) {
                v.push_back(i);
                m[i] = 1;
                dfs(i, step + 1);
                if (ans == -1) {
                    m[i] = 0;
                    v.pop_back();
                } else
                    return;
            }
        }
    }
}

int main() {
    memset(vis, 0, sizeof(vis));
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        for (int j = 0; j < n; j++)
            if (s[i][j] == 'W')
                vis[i][j] = 1;
            else if (s[i][j] == 'L')
                vis[j][i] = 1;
    }
    int flag = 1;
    for (int i = 1; i < n; i++) {
        if (vis[i][0]) {
            flag = 0;
            break;
        }
    }
    if (flag)
        printf("No Solution\n");
    else {
        ans = -1;
        v.clear();
        m.clear();
        v.push_back(0);
        m[0] = 1;
        dfs(0, 1);
        if (ans == -1)
            printf("No Solution\n");
        else {
            vector<int>::iterator it;
            for (it = v.begin(); it != v.end(); it++) {
                if (it != v.begin())
                    printf(" ");
                cout << (*it) + 1;
            }
            cout << endl;
        }
    }
}
Last update: May 4, 2022
Back to top