题目链接：https://www.patest.cn/contests/gplt/L3-015
简介：哈密顿路除了暴搜，当然还可以DP,只不过需要2n的空间，复杂度是O(n*(2n)), 暴搜不需要那么多，但复杂度为O(n!)。
ACFUN群里的讲解：
因为是个环肯定 1 是第一个点
然后你就找一条链就行了，dp[mask][i] 表示 mask 集合的最后一个点是 i 的路径是否存在
第二维还可以压位不过这个不重要
所以这实际上就是求个排列dp。
排列dp相关题目：http://www.jianshu.com/p/fdf03a78176b 的2题3题。
但这题还是有几个坑点：
- 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;
}
