• 令 $cut(x,y)$ 为 $x,y$ 的最小割的值。
• 以下的 “连通” ：存在一条 $x,y$ 的路径，其路径上边权最小值非负（等价定义为 $cut(x,y)>0$）。

一个结论

• 将 $x$ 的最小割集割掉之后，那么原图 $y$ 将被分为两个集合。（不考虑原图中与 $x,y$ 不连通的点）
• 一个集合为 $x$ 所在的连通块集合 $A$，一个集合为 $y$ 所在的集合 $B$。

证明

• 假设存在一些点不属于这两个连通块之一。
• 则这些点中必有点和 $A$ 或 $B$ 在原图中有非零边，不妨设有点与 $A$ 在原图中有非零边。
• 那么将这个连通块中与 $A$ 的边全部连回去（即不割这些边），那么 $x,y$ 依旧不连通。
• 而不割这些边后，最小割的值变小了，矛盾。
• 证毕。
• 推论0：对于 $u\in A,v\in B$，有 $cut(u,v)\leq cut(x,y)$，因为 $x,y$ 的最小割也是 $u,v$ 的割。

定理

• 任取不同的三点 $x,y,z$。
• 那么有 $\min(cut(x,z),cut(y,z))\leq cut(x,y)$。

证明

• 若 $cut(x,y)=0$，那么 $cut(x,z),cut(y,z)$ 中也必定有一个为 $0$。
• 若 $cut(x,y)\neq 0$，
  • 不妨设将 $x,y$ 的最小割集割掉之后，$z$ 属于 $x$ 所在的连通块。
  • 那么 $x,y$ 的最小割集同时也是 $z,y$ 的最小割集，即 $cut(y,z)\leq cut(x,y)$。
  • 而 $z$ 属于 $y$ 所在的连通块时，有 $cut(x,z)\leq cut(x,y)$。
• 证毕。

推论1

• 任取不同的三点 $x,y,z$。
• 当 $cut(x,y)$ 满足是 $cut(x,z),cut(y,z),cut(x,y)$ 中最小时，有 $\min(cut(x,z),cut(y,z))=cut(x,y)$。
• 此命题等价于任意三点两两最小割值必有相同。

证明

• 显然。

推论2

• 任取不同的 $k\geq 2$ 个点 $c_1,c_2,\cdots,c_k$，那么有 $\min(cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k))\leq cut(c_1,c_k)$。

证明

• $cut(c_1,c_k)\geq \min(cut(c_1,c_2),cut(c_2,c_k))$，而 $cut(c_2,c_k)\geq \min(cut(c_2,c_3),cut(c_3,c_k))$，以此类推即证。

推论3

• 任取不同的 $k\geq 3$ 个点 $c_1,c_2,\cdots,c_k$。
• 当 $cut(c_1,c_k)$ 满足是 $cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k),cut(c_1,c_k)$ 中最小时，那么有 $\min(cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k))=cut(c_1,c_k)$。
• 此命题等价于任意 $k\geq 3$ 个点两两最小割值必有相同。即最小割值互不相同的边不可能成环。

证明

• 显然。

终极目标

• 任意一张图，任意两点的最小割最多有 $n-1$ 种不同的值。

证明

• 把最小割的值当做边权建立一张完全图。不妨考虑图的任意一棵生成树。
• 依次考虑每一条在树中没出现过的权值的非树边，看它对应的树上的路径必定至少有两条边权值相同（推论3），删除其中一条边后接上这条边。
• 可以发现，做完后可以使所有完全图中权值不同的边都在生成树上，而生成树为 $n-1$ 条边，所以权值不同的边的数量也只有 $n-1$ 条。

最小割树

定义

• 如果对于树上的所有边 $(u,v)$，树上去掉 $(u,v)$ 后产生的两个集合恰好是原图上 $(u,v)$ 的最小割把原图分成的两个集合，且边 $(u,v)$ 的权值等于原图上 $(u,v)$ 的最小割。

构造

• 首先任意选择两个点，跑最小割。
• 那么把图分成的两个部分，由推论0，两个部分之间的最小割是没有影响的。
• 然后继续求解两个部分的最小割树。

性质

• 原图上 $u,v$ 两点最小割就是最小割树上 $u$ 到 $v$ 的路径上权值最小的边。
• 不妨设 $u$ 到 $v$ 的路径上的点（不包括 $u,v$）依次为 $c_1,c_2,\cdots,c_k$。
• 由推论 $3$ ，有 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\leq cut(u,v)$。
• 而对于每一条边，由推论0，$cut(u,v)\leq cut(u,c_1),cut(u,v)\leq cut(c_1,c_2),\cdots,cut(u,v)\leq cut(c_k,v)$。
• 可得 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))=cut(u,v)$。

[JZOJ5495]【清华集训2017模拟12.09】MiniumCut

• 而这道题其实就是求最小割树，两两点的最小割等于这两点在最小割树上的路径边权最小值。
• 考虑从大到小加入边，新加入一条边时，这条边比之前所有边都要小。
• 如果这条边连接的两个点已经连通了，那么两点路径上的边权最小值 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\geq cut(u,v)$。
• 又根据推论 $3$，有 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\leq cut(u,v)$。
• 故 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))=cut(u,v)$，得证。
• 最后需要判断是否合法，因为中间的推论 $3$ 是假设现在满足最小割树的性质的。