前言

似乎距离上次写学习笔记已经过去了很久很久，上一篇学习笔记还是回文自动机学习笔记。这段时间其实也学了不少东西但一直没时间写，今天就趁着稍微有点的时间来写写。

问题引入

​ 给你一个 $n$ 个点 $m$ 条边的无向连通图，边有非负边权，给定两个点 $u,v$，每次可以花费那条边边权的代价将这条边断开，问使得点 $u,v$ 不联通的最小代价。

$n\le 200,m\le 5000$

我相信聪明的你一定发现这是道水题，好吧，确实。这就是经典的最小割问题，你可以从这里拷一份代码下来飞速做出这道题。但如果我们加上多组询问呢？

​ 给你一个 $n$ 个点 $m$ 条边的无向连通图，边有非负边权，你可以花费一条边边权的代价将这条边断开，有 $q$ 次询问，每次给定两个点 $u,v$，问使得点 $u,v$ 不联通的最小代价。

$n\le 500,m\le 1500,q\le 10^5$

其实就是这道题。

算法讲解

定理 1

• 任取原图上互不相同的三个点 $x,y,z$。一定满足 $f(x,y)\geq \min \lbrace f(x,z),f(y,z)\rbrace$。

因为我们只考虑这三个点，所以如果要将点 $x,y$ 割开的话，点 $z$ 一定会和点 $x$ 或者点 $y$ 在一个连通块里。简单分类讨论一下即可证明。

• 对于任意 $k$ 个互不相同的点构成的序列 $s$，一定满足下面的式子：

注意到上面的式子是有顺序的，不是随意两个组合起来。尝试构造一个使得右式最大的情况。先不考虑右式的最后一项，那么右式就和 $s_k$ 无关了。假如我们已经构造出了这么一张图，$s_1$ 到 $s_{k-1}$ 都是联通的，那么现在连上点 $s_k$，如果 $s_k$ 连上了 $s_1$，那么一定满足 $f(s_1,s_k)\ge f(s_{k-1},s_k)$。连上其他点情况类似。

如果在这张图上 $s_k$ 是割点，也就是说在不考虑 $s_k$ 时 $s_1$ 到 $s_{k-1}$ 是不联通的，那么一定存在至少一对点分别在点 $s_k$ 的两侧。简单分讨一下也可以得出结论。

定理 2

• 若一棵树的每条边满足边权为最小割且割断此边分出的点集与最小割割出的点集相同，那么取任意两点 $u,v$，令 $s,t$ 为 $u,v$ 的路径上最小的边所连接的两个点，一定满足 $f(u,v)=f(s,t)$

根据上面定理的推论，我们有 $f(u,v)\ge f(s,t)$。且根据这颗树的定义，$s,t$ 的最小割一定可以使 $u,v$ 之间断开，所以我们有 $f(u,v)\le f(s,t)$。综上，只能 $f(u,v)=f(s,t)$。

算法流程

• 每次随便找两个在同一联通块内的点，在原图上跑一遍最小割。
• 在残量网络上看看哪些边被割开了，根据这些被割开的边将该联通块重新分为两个小联通块。并在树上将这两个点之间连一条边，边权设为最小割的代价即可。
• 这样一直分下去，直到连通块大小为 $1$ 就结束操作。