L3-015 球队“食物链” (30 分)

题目描述：

n个球队，给出一个n * n的矩阵G，G[i][j]表示球队i在主场对阵球队j的比赛结果，W表示战胜、L表示失败,D表示持平，问能否存在一个长度为n的序列a，球队各不相同，且满足a[1]胜a[2]，a[2]胜a[3], … a[i-1]胜a[i]，a[i]胜a[1]

思路：

枚举以i作为序列起始点，然后爆搜

注意要剪枝：如果当前剩余队伍中不存在能战胜第一只队伍，则就没有遍历下去的必要了

坑点：

• a[i][j]=L可以代表j 胜i，且如果a[i][j] = L,a[j][i]=L,也代表j能胜i

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
char s[25][25];
bool G[25][25];
int root;
bool vis[MAX];
int fa[MAX];

bool check(){
    for(int i = 1; i <= n; ++i){
        if(!vis[i] && G[i][root])return true;
    }
    return false;
}

void dfs(int u, int num){
    if(num == n){
        if(G[u][root]){
            vector<int>v;
            int p = u;
            while(p != root){
                v.push_back(p);
                p = fa[p];
            }
            v.push_back(root);
            reverse(v.begin(), v.end());
            for(int i = 0; i < v.size(); ++i){
                if(i)cout << ' ';
                cout << v[i];
            }
            cout << endl;
            exit(0);
        }
        else return;
    }
    if(!check())return;
    for(int v = 1; v <= n; ++v){
        if(!vis[v] && v != u && G[u][v]){
            vis[v] = 1;
            fa[v] = u;
            dfs(v, num + 1);
            vis[v] = 0;
            fa[v] = -1;
        }
    }
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= n; ++j){
            if(s[i][j] == 'W')G[i][j] = 1;
            else if(s[i][j] == 'L')G[j][i] = 1;
        }
    }
    for(int i = 1; i <= n; ++i){
        vis[i] = 1;
        root = i;
        dfs(i, 1);
        vis[i] = 0;
    }
    cout << "No Solution\n";
}


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