这题应该很容易想到DFS，但需要加个减枝。
首先我们知道，他要形成食物链必然是把五支球队都包括进去了，也就是说必然存在1吃x，y吃1。题目又要求字典序最小，那你1不排在第一个，谁还敢上啊。所以我们的DFS便是由1开始。而这恰恰为减枝铺好了路。
考虑到1在第一位，所以在食物链尾端的辣个队必然要吃掉1，也就是第一列除第一行剩下的行中要存在W。我们在每次DFS中，只要判断是否存在W即可。不存在直接结束当前DFS。
详见代码～
No Solution想当然多加了一个感叹号。。。。。。。检查了好久。。。。。。。。自罚3题。。。。退群了。。。。。
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <math.h> #include <queue> #include <vector> #include <functional> #define maxn 105 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int n,flag; char ma[maxn][maxn]; int win[maxn][maxn],ans[maxn]; int vis[maxn]; void DFS(int x,int d) { if(flag) return; if(d==n) { if(win[x][1]) { flag=1; printf("1"); for(int i=1;i<=d-1;i++) printf(" %d",ans[i]); printf("\n"); } return; } int k; for(k=2;k<=n;k++) { if(!vis[k]&&win[k][1]) break; } if(k==n+1) return; for(int i=2;i<=n;i++) { if(!vis[i]&&win[x][i]) { ans[d]=i; vis[i]=1; DFS(i,d+1); vis[i]=0; } } } int main() { flag=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",ma[i]+1); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(ma[i][j]==‘W‘) win[i][j]=1; if(ma[i][j]==‘L‘) win[j][i]=1; } } vis[1]=1; DFS(1,1); if(!flag) printf("No Solution\n"); return 0; }
原文：https://www.cnblogs.com/FTA-Macro/p/10518739.html
