Hamilton 回路的存在性！

· · 休闲·娱乐

注意到一个 Hamilton 回路是一个边权之和为 n 的环。

发现 Hamilton 回路存在等价于最大环等于 n。

尝试将所有边的权值赋为 -1，然后跑 floyd 最小环算法。

额好吧这个错得太明显了，换一个。

考虑枚举一条边 (U,V)，然后考虑判断从 U 到 V 的 Hamilton 路的存在性。也就是从 U 到 V 是否有长度为 n-1 的简单路径。

发现费用流非常万能，就考虑用它了。

为了确保每个点都只用一次，考虑拆点。

然后求从 $u$ 到 $v'$ 的最小费用最大流，如果费用为 $-n$，说明存在 Hamilton 路径。 因为所有边的流量都是 $1$，求出来的一定是单独的一条增广路不会有劈叉。而费用是 $-n$ 说明这条增广路一定经过了所有点，因此这条增广路就对应了原图中的 Hamilton 路。