团体程序设计天梯赛-练习集 L3-015 球队“食物链”

如下三个坑点:
1、所给的图非对称,因为每个队打了两场比赛,每一场分别记输赢。所以每行数据都要做处理。
2、要求食物链的字典序最小,而且该食物链是从1到n的排列,因此只要有环,头一个一定从1开始是字典序最小的状况,只需要从1开始DFS即可。
3、剪枝:不剪枝T一个点。在DFS中把经过的点标记,若未标记的点集中不存在与1连通的点,则不可能构成环状结构,直接return false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int n;
char arr[25][25];
deque<int> st;
bool visited[25];
bool dfs(int curNode,int visitedNodeCnt){
    if(visited[curNode]){
        if(visitedNodeCnt==n+1&&curNode==1)return true;
        else return false;
    }
    bool flag=false;
    for(int i=1;i<=n;i++){
        if(!visited[i]&&(arr[i][1]=='W'||arr[1][i]=='L'))flag=true;
    }
    if(!flag)return false;
    visited[curNode]=true;
    for(int i=1;i<=n;i++){
        if(i==curNode)continue;
        if(arr[curNode][i]=='W'||arr[i][curNode]=='L'){
            if(dfs(i,visitedNodeCnt+1)){
                st.push_back(i);
                return true;
            }
        }
    }
    visited[curNode]=false;
    return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",arr[i]+1);
    bool flag=dfs(1,1);
    if(!flag)printf("No Solution\n");
    else{
        printf("%d",st.front());
        st.pop_front();
        while(!st.empty()){
            printf(" %d",st.back());
            st.pop_back();
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注