qoj#11722 Hamilton

· · 个人记录

题目大意

以如下方式给出一张带权无向图：点集为 \{1,2,\dots,n\}，边有两种：

现在给定起点 a 和终点 b （保证 a\neq b），构造一条从 a 开始，以 b 结束的权值和最小的哈密顿路径（即经过每个点恰好一次），或报告无解。

### 解题过程 不妨设 $a<b$，否则交换 $a,b$ 并将路径首尾翻转即可。 观察到边权为 $1$ 的边实际上是很多的，所有可以猜想路径权值和较小。注意到路径权值和实际上就是有多少条 $(i,i+1)$ 的边没有经过，称这种边为"断边"。由于 $a,b$ 为路径端点，所以 $(a,a+1)$ 和 $(a-1,a)$ 中至少一条断边，$(b,b+1)$ 和 $(b-1,b)$ 中至少一条断边，即当 $1<a<b<n$ 且 $b-a>1$ 时答案至少为 $2$，故可以分类讨论所有答案不超过 $2$ 的情况。 （下文中 $a\to b$ 表示边权为 $0$ 的边，要求 $|a-b|=1$；$a\Rightarrow b$ 表示边权为 $1 $ 的边，要求 $\gcd(a,b)=1$；$a\leadsto b$ 表示通过 $0$ 的边从 $a$ 到 $b$ 的路径，即 $a<b$ 时为 $a\to a+1\to\dots\to b$，$a>b$ 时为 $a\to a-1\to\dots\to b$，$a=b$ 时即表示单点 $a$）： 答案为 $0$ 的情况： 1. 只有 $a\leadsto b$，此时要求 $a=1,b=n$。 答案为 $1$ 的情况： 1. $a\leadsto 1\Rightarrow n\leadsto b$，此时要求 $a+1=b$； 2. $a\leadsto 1\Rightarrow a+1\leadsto b$，此时要求 $b=n$； 3. $a\leadsto b-1\Rightarrow n\leadsto b$，此时要求 $a=1$ 且 $\gcd(n,b-1)=1$。 答案为 $2$ 的情况： 1. $a\leadsto 1\Rightarrow b-1\leadsto a+1\Rightarrow n\leadsto b$，要求 $\gcd(a+1,n)=1$； 2. $a\leadsto 1\Rightarrow a+1\leadsto b-1\Rightarrow n\leadsto b$，要求 $\gcd(b-1,n)=1$； 3. $a\leadsto b-1\Rightarrow 1\leadsto a-1\Rightarrow n\leadsto b$，要求 $\gcd(a-1,n)=1$； 4. $a\leadsto b-1\Rightarrow a-1\leadsto 1\Rightarrow n\leadsto b$，要求 $\gcd(a-1,b-1)=1$； 5. $a\leadsto 1\Rightarrow b+1\leadsto n\Rightarrow a+1\leadsto b$，要求 $\gcd(a+1,n)=1$（这实际上和 1 解决的是同一种情况）； 6. $a\leadsto 1\Rightarrow n\leadsto b+1\Rightarrow a+1\leadsto b$，要求 $\gcd(a+1,b+1)=1$。 7. 还有部分 $a=1$ 的剩余情况。 考虑剩余情况，即上面的互质条件都不满足，最简单的例子就是 $n$ 为偶数，$a,b$ 均为奇数。 简单举例尝试一下，可以发现这种情况似乎不存在构造。事实上，这就是本题的无解情况，证明如下：采用上面的“断边”来刻画哈密顿路径，那么每条断边的端点一定是一奇一偶，又因为 $1$ 为奇数，$n$ 为偶数，所以设断点将 $[1,n]$ 分成了 $c$ 段（这意味着如果存在路径，边权和为 $c-1$），那么所有段的左右端点加起来共有 $c$ 个奇数 $c$ 个偶数。又因为起点 $a$ 终点 $b$ 均为奇数，所以剩余的 $c-2$ 个奇数 $c$ 个偶数分成 $c-1$ 对（每对代表一条段之间的连边），必然有一对偶数，那么此时就不可能互质，这两个点之间不可能存在边。 上面的证明也提示了考虑奇偶性，所以对于剩余的情况考虑将 $(1,2)$ 设为断边，这样 $2$ 和所有奇数之间都有权值为 $1$ 的边： 对于 $a=1$（这就是上面没讨论的权值和为 $2$ 的情况）： 1. $n$ 为奇数：$1\Rightarrow b-1\leadsto 2\Rightarrow n\leadsto b$； 2. $b$ 为偶数：$1\Rightarrow n\leadsto b+1\Rightarrow 2\leadsto b$。 对于 $a>1$（权值和为 $3$）： 1. $n$ 为奇数：$a\leadsto2\Rightarrow n\leadsto b+1\Rightarrow 1\Rightarrow a+1\leadsto b$； 2. $b$ 为偶数：$a\leadsto2\Rightarrow b+1\leadsto n\Rightarrow 1\Rightarrow a+1\leadsto b$； 3. $a$ 为偶数：$a\leadsto2\Rightarrow a+1\leadsto b-1\Rightarrow 1\Rightarrow n\leadsto b$； 除了分类讨论外，另一种可能的思路是暴力枚举断边（上面用到的断边只有五种可能）并枚举每段之间的顺序、每段内的方向并检验，可以避免讨论。