团体程序设计天梯赛-练习集 L3-015. 球队“食物链”(DFS)

Description:

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

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

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

注：排列{ a1 a2 …aN }在字典序上小于排列{ b1 b2 … bN }，当且仅当存在整数K（1 <= K <= N），满足：aK < bK且对于任意小于K的正整数i，ai=bi。

Input:

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

Output:

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

Sample Input:

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

Sample Output:

1 3 5 4 2

Sample Input:

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

Sample Output:

No Solution

题目链接

题目用深搜从字典序最小开始搜索出一条完整的回路即可，在搜索中需要用到剪枝即当剩下所有球队都没有赢过1号球队时就没有球队可以放在最后一位此次深度优先搜索失败。

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 22;
const double eps = 1e-5;
const double e = 2.718281828459;

int n;
int cnt = 0;
bool flag[maxn];
char rel[maxn][maxn];
int ans[maxn];
bool res_flag = 0;

void dfs(int st, int step) {
    if (step == n && (rel[st][1] == 'W' || rel[1][st] == 'L')) {
        ans[step] = st;
        res_flag = 1;
        return;
    }
    else {
        // 剪枝
        bool dfs_flag = 0;
        for (int i = 1; i <= n; ++i) {
            if (!flag[i] && (rel[i][1] == 'W' || rel[1][i] == 'L')) {
                dfs_flag = 1;
                break;
            }
        }
        if (!dfs_flag) {
            return;
        }
        // 搜索
        for (int i = 1; i <= n; ++i) {
            if (!flag[i] && (rel[st][i] == 'W' || rel[i][st] == 'L')) {
                flag[i] = 1;
                ans[step] = st;
                dfs(i, step + 1);
                if (res_flag) {
                    return;
                }
                flag[i] = 0;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> rel[i][j];
        }
    }
    mem(flag, 0);
    flag[1] = 1;
    dfs(1, 1);
    if (!res_flag) {
        cout << "No Solution";
    }
    else {
        cout << ans[1];
        for (int i = 2; i <= n; ++i) {
            cout << " " << ans[i];
        }
    }
    return 0;
}