天梯赛L3 015 - 球队“食物链” (DFS剪枝)

某国的足球联赛中有N支参赛球队，编号从1至N。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。
联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个1至N的排列{ T1 T2 ⋯ TN }
现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”，请找出字典序最小的。
注：排列{ a1 a2 … aN​​ }在字典序上小于排列{ b1, b2 … bn }, 当且仅当存在整数K（1≤K≤N），满足：a​K < b​K, 且对于任意小于K的正整数i，a​i = 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

参考资料

知识点：
状压dp：
1.状态压缩（初识）
2.【原创】【状态压缩DP】POJ3254 Corn Fields【新手向】
哈密顿回路：
1.哈密顿回路
2.哈密顿图 哈密顿回路 哈密顿通路(Hamilton)

题解：
1.团体程序设计天梯赛-练习集 – L3-015. 球队“食物链”（状压+dfs 求哈密顿回路）
2.CCCC天梯赛 L3-015. 球队“食物链”
3.PAT-练习集-L3-015. 球队“食物链”
4.5-15 球队“食物链” (30分) – L3-015. 球队“食物链” (2017天梯初赛 剪枝dfs)

思路

看了很多思路, 看到那些啥哈密顿回路吖,状压dp吖一度想放弃来着, 幸好发现了有个DFS剪枝的思路(题解链接4)能理解了=_=

萌新AC代码如下, 欢迎指点
处理思路都在注释里~

AC代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mst(a) memset(a,0,sizeof(a));

using namespace std;
const int maxn = 20 + 1;
int g[maxn][maxn], vis[maxn], s[maxn];
bool ok;
int n, baba;

bool bigcut(){ //大剪枝,如果有球队未赢过或者没人赢过1队, 直接no solution
    for( int i = 1; i <= n; i++ ){
        bool flag = false;
        for( int j = 1; j <= n; j++ )
            if( g[i][j] == 1 ) { flag = true; break; }
        if( !flag )  return false;
    }
    for( int i = 2; i <= n; i++ )  //如果有人能战胜1队
        if( g[i][1] == 1 )  return true;
    return false;
}

bool smcut(){  //小剪枝,如果此刻未访问的点都没赢过1, 一定不成环
    int i;
    for( i = 1; i <= n; i++ ){
        if( !vis[i] && g[i][1] == 1 )
            break;
    }
    if( i > n ) return false;
    return true;
}

void Print(){
    for( int i = 1; i <= n ; i++ ){
        if( i != 1 )    printf(" ");
        printf("%d",s[i]);
    }
    putchar('\n');
    return;
}

void dfs(int x, int d){
    vis[x] = 1;
    s[d] = x;
    if( d == n ){
        if( g[x][baba] == 1 ){ //判断是否成环
            ok = true;
            return;
        }
    }
    if( !smcut() ) return;  //小剪枝
    for( int i = 1; i <= n; i++ ){
        if( !vis[i] && g[x][i] == 1 ){
            vis[i] = 1;
            dfs( i, d+1 );
            if(ok) return;
            vis[i] = 0;  //回溯
        }
    }
}

int main()
{
    char ch;
    while( ~scanf("%d",&n) ){
        getchar();
        mst(g);
        for( int i = 1; i <= n; i++ ){
            for( int j = 1; j <= n; j++ ){
                scanf("%c",&ch);
                if( ch == 'W' ) g[i][j] = 1; //i赢过j 直接标记g[i][j] = 1;
                else if( ch == 'L' ) g[j][i] = 1; //i输给过j(j赢过i) 直接标记g[j][i] = 1;
            }
            getchar();
        }
        ok = false;
        if( !bigcut() ){
            puts("No Solution");
            continue;
        }
        for( baba = 1; baba <= n; baba++ ){ //按字典序,循环枚举每次排在食物链第一的序号
            mst(vis);
            dfs(baba, 1);
            if( ok ){ Print(); break; }
        }
        if( baba > n )   puts("No Solution");
    }
    return 0;
}