Hamilton 回路的存在性！

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

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

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

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

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

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

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

$(u,u')$ 连一条费用为 $-1$，流量为 $1$ 的边。对于原图的边 $(u,v)$，$(u',v)$ 和 $(v',u)$ 各连一条费用为 $0$，流量为 $1$ 的边。

然后求从 $u$ 到 $v'$ 的最小费用最大流，如果费用为 $-n$，说明存在 Hamilton 路径。

因为所有边的流量都是 $1$，求出来的一定是单独的一条增广路不会有劈叉。而费用是 $-n$ 说明这条增广路一定经过了所有点，因此这条增广路就对应了原图中的 Hamilton 路。