Description
大家最喜欢的典中典环节它来了。
在图论中，无向图的哈密顿路径是恰好能将图中所有顶点各访问一次的路径。
给定一张 \(n\) 个点的简单无向图。对于每个 \(1 \leq x, y \leq n(x \neq y)\)，你想要知道，是否存在一条以顶点 \(x\) 为起点, 以顶点 \(y\) 为终点的哈密顿路径。
\(2\%\) 的数据，\(n\le 9\)。
\(38\%\) 的数据，\(n\le 19\)。
\(100\%\) 的数据，\(n\le 24\)。
Solution
\(2\%\) 数据
设布尔数组 \(f_{s,i,j}\) 表示起点为 \(i\)，当前点为 \(j\)，经过的点集为 \(s\) 的情况是否存在。
转移枚举起点，然后枚举当前点 \(j\) 和点集 \(s\),再枚举 \(k\) 表示从 \(k\) 到 \(j\)。则，\(f_{s,i,j}=f_{s-2^{j-1},i,k}\)。
时间复杂度 \(\mathcal O(2^nn^3)\)。
\(38\%\) 数据
\(f\) 开成布尔类型太亏了，设 \(f_{s,i}\) 表示当前点为 \(i\)，点集为 \(s\) 的可能起点（通过二进制来对应）。
初始时 \(f_{2^{i-1},i}=2^{i-1}\)，枚举点集 \(s\) 和当前点 \(i\)，再枚举点 \(j\) 表示从 \(j\) 转移到 \(i\)。\(f_{s,i}|=f_{s-2^{i-1},j}\)。
时间复杂度 \(\mathcal O(2^nn^2)\)。注意空间。
\(100\%\) 数据
多个起点不太优秀，考虑优化。
根据哈密顿路径的定义，节点 1 一定在路径上。同时我们可以将路径 \(x\rightarrow y\) 变成 \(1\rightarrow x\) 和 \(1\rightarrow y\)。
设 \(f_s\) 表示从 1 开始，经过点集为 \(s\) 的点，最后可能停在哪些点。记 \(g_i\) 表示能到达点 \(i\) 的点。转移则枚举 \(s\) 和当前点 \(i\)，那么 \(i\) 能作为终点，当且仅当存在 \(j\in f_{s-2^{i-1}}\) 且 \(j\in g_i\)，即 \(f_{s-2^{i-1}} \text{ and } g_i\not=0\)。
统计答案则根据 Meet in the Middle 的想法,枚举 \(S\)，则\(T=U-S\)（\(U\) 是全集）。再枚举 \(i\in S\)，用 \(f_T\) 去更新 \(i\) 的答案。
时间复杂度 \(\mathcal O(2^nn)\)。
Code
#include<cstdio>
#include<cstring>
#define N 30
#define MX (1<<24)+5
using namespace std;
int n,f[MX],g[N],ans[N];
char ch[N];
int main()
{
freopen("hamilton.in","r",stdin);
freopen("hamilton.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%s",ch+1);
for (int j=1;j<=n;++j)
if ((ch[j]-'0')==1) g[j]+=1<<(i-1);
}
f[1]=1;
for (int s=2;s<(1<<n);++s)
{
for (int i=1;i<=n;++i)
if (s&(1<<(i-1)))
{
int ss=s^(1<<(i-1));
if (f[ss]&g[i]) f[s]+=1<<(i-1);
}
}
ans[1]=f[(1<<n)-1];
for (int s=1;s<(1<<n);s+=2)
{
int t=((1<<n)-1)^s;
for (int i=2;i<=n;++i)
if (f[s]&(1<<(i-1)))
ans[i]|=f[t|1];
}
for (int i=1;i<=n;++i)
{
for (int j=1;j<=n;++j)
if (ans[i]&(1<<(j-1))) printf("1");
else printf("0");
printf("\n");
}
return 0;
}