題目鏈接：https://www.patest.cn/contests/gplt/L3-015
簡介：哈密頓路除了暴搜羊初，當(dāng)然還可以DP,只不過需要2n的空間街立，復(fù)雜度是O(n*(2n)), 暴搜不需要那么多舶衬，但復(fù)雜度為O(n!)。
ACFUN群里的講解：
因?yàn)槭莻€(gè)環(huán)肯定 1 是第一個(gè)點(diǎn)
然后你就找一條鏈就行了赎离，dp[mask][i] 表示 mask 集合的最后一個(gè)點(diǎn)是 i 的路徑是否存在
第二維還可以壓位不過這個(gè)不重要
所以這實(shí)際上就是求個(gè)排列dp约炎。
排列dp相關(guān)題目：http://www.reibang.com/p/fdf03a78176b 的2題3題。
但這題還是有幾個(gè)坑點(diǎn)：
- i勝過j 是 tb[i][j]=='W'||tb[j][i]=='L' ,tb[i][j] 和tb[j][i] 不相關(guān)。
- n的范圍好像是21...
- 打印路徑還是有難度和坑點(diǎn)的圾浅，首先逆推建能到終點(diǎn)的路徑圖掠手，然后從起點(diǎn)正推，坑點(diǎn)就是假設(shè)每個(gè)子集為圖上的點(diǎn)狸捕，每次選則的球隊(duì)為邊喷鸽，并不是只要到達(dá)這結(jié)點(diǎn)，由這結(jié)點(diǎn)出發(fā)的任意邊的任意邊都可以選,還和你到這點(diǎn)最后走的邊有關(guān)
代碼
#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;
}
