7-15 球队“食物链” （30 分)【 DFS + 剪枝】
7-15 球队“食物链” （30 分)【 DFS + 剪枝】
7-15 球队“食物链” （30 分)
某国的足球联赛中有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个字符，给出了N×N的联赛结果表，其中第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记录路径就没了。 不过，需要把一些直接不可能符合的情况剪掉，这样才能过掉所有的样例。 &：因为要形成环，而且字典序最小，直接从零开始搜索就行，搜索的时候记得判断在剩下的球队中是不是有球队可以胜过第一个球队，如果没有就return。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 50;
int a[maxn][maxn];
int vis[maxn],path[maxn];
int f;
int n;
void dfs(int x, int k)
{
if(f) return;
path[k] = x;
if(k == n - 1)
{
if(a[x][0] == 1)f = 1;
return ;
}
int flag = 1;
for(int i = 0; i < n; i ++)
{
if(!vis[i] && a[i][0]) flag = 0;
}
if(flag)return;
for(int i = 0; i < n; i ++)
{
if(!vis[i] && a[x][i])
{
vis[i] = 1;
dfs(i,k + 1);
vis[i] = 0;
}
}
}
char s[50];
int main()
{
scanf("%d",&n);
memset(a,0,sizeof(a));
for(int i = 0; i < n; i ++)
{
scanf("%s", s);
for(int j = 0; j < n; j ++)
{
if(s[j] == 'W')a[i][j] = 1;
else if(s[j] == 'L')a[j][i] = 1;
}
}
memset(vis,0,sizeof(vis));
vis[0] = 1;
f = 0;
dfs(0,0);
if(f)
{
for(int i = 0; i < n; i ++)
{
if(i == 0) printf("%d",path[i] + 1);
else printf(" %d",path[i] + 1);
}
printf("\n");
}
else printf("No Solution\n");
return 0;
}腾讯云开发者
