哈密顿回路， DP解法

因为是个环肯定 1 是第一个点
然后你就找一条链就行了，dp[mask][i] 表示 mask 集合的最后一个点是 i 的路径是否存在
第二维还可以压位不过这个不重要

i胜过j 是 tb[i][j]=='W'||tb[j][i]=='L' ,tb[i][j] 和tb[j][i] 不相关。
n的范围好像是21...
打印路径还是有难度和坑点的，首先逆推建能到终点的路径图，然后从起点正推，坑点就是假设每个子集为图上的点，每次选则的球队为边，并不是只要到达这结点，由这结点出发的任意边的任意边都可以选,还和你到这点最后走的边有关
代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXS = 1<<21;
const int MAXN = 21;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> pii;
int dp[MAXS], G[MAXS][MAXN], n;
char tb[MAXN][MAXN];
inline bool win(int x, int y) {
    return tb[x][y]=='W'||tb[y][x]=='L';
}
inline bool of(int x, int st) {
    return (1<<x)&st;
}
bool bfs() {
    queue<pii> q;
    while(q.size()) q.pop();
    memset(G, 0x3f, sizeof(G));
    int t=(1<<n)-1;
    bool ret=false;

    for(int i=0; i<n; ++i)
        if(of(i,dp[t])&&win(i,0))
            q.push(make_pair(t,i));
    while(q.size()) {
        pii u= q.front();
        q.pop();
        int nst = u.first^(1<<u.second);
        if(nst) {
            for(int i=0; i<n; ++i)
                if(of(i,dp[nst])&&win(i,u.second)) {
                    if(G[nst][i]==INF) q.push(make_pair(nst,i));
                    G[nst][i] = min(G[nst][i], u.second);
                }
        }
        else {
            ret = true;
            G[0][0] = 0;
        }
    }
    return ret;
}
void printpath() {
    int st=0, p=0;
    while(G[st][p]<INF) {
        if(st) putchar(' ');
        printf("%d", G[st][p]+1);
        p = G[st][p];
        st |= 1<<p;
    }
    puts("");
}
int main() {
    scanf("%d", &n);
    for(int i=0; i<n; ++i)
        scanf("%s", tb[i]);
    dp[1] = 1;
    for(int st=1; st<(1<<n)-1; ++st) {
        int b[MAXN], sz=0;
        for(int i=0; i<n; ++i)
            if(of(i,dp[st])) b[sz++] = i;
        for(int i=0; i<sz; ++i)
            for(int j=0; j<n; ++j)
                if(win(b[i],j)&&!of(j,st))
                    dp[st|(1<<j)] |= (1<<j);
    }
    if(bfs()) printpath();
    else puts("No Solution");
    return 0;
}

全部频道

哈密顿回路， DP解法