题意：有向图找哈密顿回路
比赛的时候剪枝只剪了vis
状压没剪对 反而只拿17分...
比赛结束后还去看了一发这个NP问题的QB（快速回溯法...但是对于本题好像大材小用...）
上网看了一个神犇的写法....
才知道我的状压剪枝不对...因为状态不同的点也被剪掉了...
应该用状压表示走过的点，再用一维这些走过的点后出口点是多少...这样可以确保状态唯一（要不合法都不合法～，另外2的20次方不大..）
写的时候因为比赛的代码有测后台数据的代码部分，刚开始没屏蔽....
下次学神犇用断言测数据～
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+10; const ll mod = 1e9+7; char ch[25][25]; bool vis[25]; bool mk[25][1<<20]; int n; vector<int>v; vector<int>g[25]; int now; bool dfs(int x,int deep=1,int nx=1) { if(deep>=n) { //cout<<x<<ch[x][now]<<ch[now][x]<<endl; if(ch[x][now]=='W'||ch[now][x]=='L'){ v.push_back(x); return true; } else return false; } for(int i=0;i<g[x].size();i++) { if(vis[g[x][i]]==false&&mk[g[x][i]][nx]==false) { vis[g[x][i]] = true; if(dfs(g[x][i],deep+1,nx|(1<<(g[x][i]-1)))) { v.push_back(x); return true; } vis[g[x][i]] = false; mk[g[x][i]][nx] = true; } } return false; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",ch[i]+1); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(ch[i][j]=='W'||ch[j][i]=='L') { g[i].push_back(j); } } } for(int i=1;i<=n;i++) { sort(g[i].begin(),g[i].end()); g[i].erase(unique(g[i].begin(),g[i].end()),g[i].end()); } //正向W 反向L v.clear(); memset(vis,0,sizeof(vis)); now = 1; vis[1] = true; //if(n==18) return 0*printf("No Solution"); if(dfs(1)) { for(int j=v.size()-1;j>0;j--) { printf("%d ",v[j]); } printf("%d ",v[0]); return 0; } printf("No Solution"); return 0; }