某国的足球联赛中有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。
输入格式：
输入第一行给出一个整数N（2 <= N <= 20），为参赛球队数。随后N行，每行N个字符，给出了NxN的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：“W”表示球队i战胜球队j，“L”表示球队i负于球队j，“D”表示两队打平，“-”表示无效（当i=j时）。输入中无多余空格。
输出格式：
按题目要求找到“食物链”T1 T2 ... TN，将这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
八分的测试点总是超时，然后就改成邻接表，还是超时，学习了别人的方法，dfs到一个位置，可以查看如果剩下没访问的点都没有赢过第一个点的话，就返回，因为继续dfs下去没意义。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; char s[30]; int ss[30]; int n,visited[30]; int u[400],v[400],fir[400],nex[400],c,mp[30][30]; int flag; int print() { printf("%d",ss[0]); for(int i = 1;i < n;i ++) { printf(" %d",ss[i]); } } void dfs(int k,int t) { if(flag)return; if(t == n) { if(mp[ss[n - 1]][ss[0]]) { flag = 1; print(); } return; } int c = 0; for(int i = 1;i <= n;i ++) { if(!visited[i] && mp[i][ss[0]])c ++; } if(!c)return; int a = fir[k]; while(a != -1) { if(flag)return; if(!visited[v[a]]) { visited[v[a]] = 1; ss[t] = v[a]; dfs(v[a],t + 1); visited[v[a]] = 0; } a = nex[a]; } } int main() { scanf("%d",&n); memset(fir,-1,sizeof(fir)); for(int i = 0;i < n;i ++) { scanf("%s",s); for(int j = n - 1;j >= 0;j --) { if(s[j] == 'W') { mp[i + 1][j + 1] = 1; } else if(s[j] == 'L') { mp[j + 1][i + 1] = 1; } } } for(int i = 1;i <= n;i ++) { for(int j = n;j >= 1;j --) { if(mp[i][j]) { u[c] = i; v[c] = j; nex[c] = fir[u[c]]; fir[u[c]] = c ++; } } } for(int i = 1;i <= n;i ++) { if(!flag) { ss[0] = i; visited[i] = 1; dfs(i,1); visited[i] = 0; } else break; } if(!flag)puts("No Solution"); }
思维要灵活，得会剪枝。。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <map> #include <algorithm> #define inf 0x3f3f3f3f using namespace std; char s[22][22]; bool vis[22],al[22]; int n,all; vector<int> ans,tans; vector<int> Next[21]; void dfs(int k) { if(!ans.empty() || tans.size() < n && all == 0) return; if(tans.size() == n) { if(s[k][1] == 'W' || s[1][k] == 'L') { ans = tans; } return; } for(int i = 0;i < Next[k].size();i ++) { if(!ans.empty()) return; if(!vis[Next[k][i]]) { tans.push_back(Next[k][i]); all -= al[Next[k][i]]; vis[Next[k][i]] = 1; dfs(Next[k][i]); vis[Next[k][i]] = 0; all += al[Next[k][i]]; tans.pop_back(); } } } int main() { scanf("%d",&n); int flag = 1; for(int i = 1;i <= n;i ++) { scanf("%s",s[i] + 1); for(int j = 1;j <= n;j ++) { if(s[i][j] == 'W') { Next[i].push_back(j); } else if(s[i][j] == 'L') { Next[j].push_back(i); } } } for(int i = 1;i <= n;i ++) { if(s[i][1] == 'W' || s[1][i] == 'L') { all ++; al[i] = true; } if(Next[i].empty()) flag = 0; sort(Next[i].begin(),Next[i].end()); } tans.push_back(1); vis[1] = 1; if(flag) dfs(1); if(ans.empty()) { printf("No Solution"); } else { for(int i = 0;i < n;i ++) { if(i) putchar(' '); printf("%d",ans[i]); } } }