题意:
某国的足球联赛中有N支参赛球队,编号从1至N。联赛采用主客场双循环赛制,参赛球队两两之间在双方主场各赛一场。
联赛战罢,结果已经尘埃落定。此时,联赛主席突发奇想,希望从中找出一条包含所有球队的“食物链”,来说明联赛的精彩程度。“食物链”为一个1至N的排列{ T?1?? T?2?? ? T?N?? },满足:球队T?1??战胜过球队T?2??,球队T?2??战胜过球队T?3??,?,球队T?(N?1)??战胜过球队T?N??,球队T?N??战胜过球队T?1??。
现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”,请找出字典序最小的。
思路:
这题就是dfs+剪枝,我一开始没有注意到给出的矩阵是不对称的,也就不是以循环赛的形式给出,然后也没注意到因为食物链是循环的,所以如果有解那么1一定在开头,只要以1递归即可。
然后这题时间要求比较高,需要很多剪枝,我一开始用dfs+回溯写有两个点超时,下面是参考网上的代码。
#include<bits/stdc++.h>
using namespace std;
const int maxn=50;
bool v[maxn][maxn];
int n;
bool vis[maxn];
bool flag;
int result[maxn];void dfs(int index,int num){if(flag==true) return ;result[index]=num;if(index==n&&v[num][1]){flag=true;return ;}if(index==n) return ;bool cnt=false;for(int i=1;i<=n;i++){if(!vis[i]&&v[i][1]){cnt=true;break;}}if(cnt==false) return;vis[num]=true;for(int i=1;i<=n;i++){if(!vis[i]&&v[num][i]){dfs(index+1,i);}}vis[num]=false;
}int main(){scanf("%d",&n);string s;for(int i=1;i<=n;i++){cin>>s;for(int j=0;j<s.size();j++){if(s[j]=='W'){v[i][j+1]=true;}else if(s[j]=='L'){v[j+1][i]=true;}}}flag=false;dfs(1,1);if(flag){for(int i=1;i<=n;i++){if(i!=1) printf(" ");printf("%d",result[i]);}}else{printf("No Solution");}return 0;
}