GPLT L3-015. 球队“食物链” dfs回溯+小剪枝

题目链接戳这里

题目大意:许多球队之间有输赢关系,求一条用字典序最小来表示的链环, a->b..->z 使得前一个队伍赢过后一个队伍,既然是环,那么z->a也要成立.

注意点:

• 单向边建立的依据是"赢过",对于a队而言,a赢b和b输a,都要有一条a->b.
• 如果能成环,始终可以把1号队伍转到第一个位置,所以直接从第一个队伍开始dfs(所以一开始要在最外层vis[0]=1),第一个解即是字典序最小的答案.
• 再而要减枝才能过第四个数据点,方法是判断后续所有队伍是否有队伍赢过第一个队伍,若根本就没有,也就无从构成环,直接return.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
const int inf = 0x3f3f3f3f, maxN = 25;
int N, M;
char CG[maxN][maxN];
int G[maxN][maxN], vis[maxN], way[maxN];

bool dfs(int s, int cnt) {
    way[cnt] = s + 1;
    if (cnt == N - 1) {
        if (!G[s][0])
            return 0;
        return 1;
    }

    int idx = 0;
    for (idx = 0; idx < N; ++idx)
        if (!vis[idx] && G[idx][0])
            break;
    if (idx == N)
        return 0;

    rep(i, 0, N) {
        if (!vis[i] && G[s][i]) {
            vis[i] = 1;
            if (dfs(i, cnt + 1))
                return 1;
            vis[i] = 0;
        }
    }
    return 0;
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d", &N);
    rep(i, 0, N) {
        scanf("%s", CG[i]);
        rep(j, 0, N) {
            if (CG[i][j] == 'W')
                G[i][j] = 1;
            else if (CG[i][j] == 'L')
                G[j][i] = 1;
        }
    }
    vis[0] = 1;
    if (dfs(0, 0)) {
        rep(i, 0, N) {
            if (i) printf(" ");
            printf("%d", way[i]);
        }
    } else {
        puts("No Solution");
    }
    return 0;
}