CCCC天梯賽 L3-015. 球隊“食物鍊”

哈密頓回路問題，很經典。（但弱雞的我，第一次做哈密頓回路的題。。。。）

這題有坑，比賽的時候被坑了兩個點，6分WA掉了。

比賽采用主客場雙循環賽制，也就是說，可能出現A赢了B，B也赢了A，或者A輸給了B，B也輸給了A的情況。

神坑。。。

然後單純的dfs，會T。比賽的時候8分T掉了。。。

首先，因為要輸出字典序最小。是以，可以直接從1開始搜尋。如果搜不到，那麼從其他點開始也是搜不到的。

然後不光對節點要打vis标記，對路徑也要打vis标記，不然就會T。（20的階乘。。。）

#include <bits/stdc++.h>
using namespace std;

const int MAXN=25;
char mz[MAXN][MAXN];
vector<int> vec[MAXN];
int n,now[MAXN],ans[MAXN];
bool vis[MAXN],pathvis[MAXN][1<<21];

int dfs(int x,int deep,int path)
{
	now[deep]=x;
	if(deep==n-1)
	{
		if(mz[x][1]=='W'||mz[1][x]=='L')
		{
			for(int i=0;i<n;i++)
				ans[i]=now[i];
			return 1;
		}
		else
			return 0;
	}
	for(int i=0;i<vec[x].size();i++)
	{
		if(vis[vec[x][i]]||pathvis[vec[x][i]][path|(1<<(x-1))])
			continue;
		vis[vec[x][i]]=1;
		if(dfs(vec[x][i],deep+1,path|(1<<(x-1))))
			return 1;
		vis[vec[x][i]]=0;
		pathvis[vec[x][i]][path|(1<<(x-1))]=1;
	}
	return 0;
}

int main()
{
	int i,j;
	while(~scanf("%d",&n))
	{
		for(i=1;i<=n;i++)
			vec[i].clear();
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				scanf(" %c",&mz[i][j]);
				if(mz[i][j]=='W')
					vec[i].push_back(j);
				else if(mz[i][j]=='L')
					vec[j].push_back(i);
			}
		}
		for(i=1;i<=n;i++)
		{
			sort(vec[i].begin(),vec[i].end());
			vec[i].erase(unique(vec[i].begin(),vec[i].end()),vec[i].end());
		}
		memset(vis,0,sizeof(vis));
		memset(pathvis,0,sizeof(pathvis));
		vis[1]=1;
		if(dfs(1,0,1))
		{
			printf("1");
			for(i=1;i<n;i++)
				printf(" %d",ans[i]);
			puts("");
		}
		else
			printf("No Solution\n");
	}
}