題意：

某國的足球聯(lián)賽中有N支參賽球隊(duì)，編號(hào)從1至N。聯(lián)賽采用主客場(chǎng)雙循環(huán)賽制，參賽球隊(duì)兩兩之間在雙方主場(chǎng)各賽一場(chǎng)。

聯(lián)賽戰(zhàn)罷，結(jié)果已經(jīng)塵埃落定。此時(shí)，聯(lián)賽主席突發(fā)奇想，希望從中找出一條包含所有球隊(duì)的“食物鏈”，來說明聯(lián)賽的精彩程度。“食物鏈”為一個(gè)1至N的排列{?T?1???T?2?????T?N???}，滿足：球隊(duì)T?1??戰(zhàn)勝過球隊(duì)T?2??，球隊(duì)T?2??戰(zhàn)勝過球隊(duì)T?3??，?，球隊(duì)T?(N?1)??戰(zhàn)勝過球隊(duì)T?N??，球隊(duì)T?N??戰(zhàn)勝過球隊(duì)T?1??。

現(xiàn)在主席請(qǐng)你從聯(lián)賽結(jié)果中找出“食物鏈”。若存在多條“食物鏈”，請(qǐng)找出字典序最小的。

思路:

這題就是dfs+剪枝，我一開始沒有注意到給出的矩陣是不對(duì)稱的，也就不是以循環(huán)賽的形式給出，然后也沒注意到因?yàn)槭澄镦準(zhǔn)茄h(huán)的，所以如果有解那么1一定在開頭，只要以1遞歸即可。

然后這題時(shí)間要求比較高，需要很多剪枝，我一開始用dfs+回溯寫有兩個(gè)點(diǎn)超時(shí)，下面是參考網(wǎng)上的代碼。

#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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/seasonal/p/10343592.html

總結(jié)

以上是生活随笔為你收集整理的L3-015 球队“食物链”（dfs）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。