暴力算法

对于 $1-2$ 测试点, 可以采用枚举边选或不选的方式通过.

时间复杂度 $\Theta(2^m)$ , 期望得分 $10$ 分.

A*算法

对于 $3-6$ 测试点, 考虑到 $m$ 比较小, $A*$ 算法其实是非常快的.

下面解释一下 $A*$ 算法：

$A*$ 算法其实就是要维护一个优先队列, 一开始只有一个状态, 就是所有边都没有被决定. 每个状态有一个估价函数, 就是已经决定的割边的边权和加上尚未决定边的最小割. 每次从优先队列中挑出估价函数最小的, 决定下一条边割或不割, 再放入优先队列中.

重复 $k$ 次, 时间复杂度 $\Theta(km\cdot networkflow(n,m))$ , 期望得分 $30-40$ 分.

针对有特殊条件的数据

对于 $7-14$ 测试点, $n, m, k$ 都比较大, 有特殊条件. 问题可以转化成有 $n-2$ 个集合, 每个集合里有 $a, b, a+b$ 这三个元素, 求前 $k$ 种方案.

K短路 不难发现, 求前 $k$ 种方案, 其实就是把 $1$ 号到 $n-2$ 号集合用权值为 $a, b, a+b$ 的边连起来, 然后求 $k$ 短路. 使用俞鼎力可持久化堆算法求 $k$ 短路, 时间复杂度 $\Theta(n \log{n}+m+k \log{k})$ , 可以通过这一部分的测试点.

优先队列 这种做法在考场上是最多人写的. 不妨定义每个集合中 $a \leq b$ , 那么最优解肯定就是全选 $a$ 了. 接下来既然都选择了 $a$ , 每个集合都只剩下了 $0, b-a, b$ , 按照第一关键字 $b-a$ 升序, 第二关键字 $b$ 升序排序. 优先队列初始时只有最优解, 优先队列的元素需要保存三个状态：当前解的答案, 当前选择到第几个集合, 当前选择的是 $0$ , $b-a$ 还是 $b$ .

每次从优先队列取出当前解答案最小的, 作如下 $3$ 种扩展：

1) 将当前集合的选择升级（ $0$ 变成 $b-a$ , $b-a$ 变成 $b$ ）；

2) 选择下一个集合, 将下一个集合的选择升级；

3) 将当前集合降级, 选择下一个集合, 将下一个集合的选择升级.

将扩展出来的状态加入优先队列, 并注意扩展的状态不要重复也不要遗漏.

重复 $k$ 次. 时间复杂度 $\Theta(n \log{n}+k \log{k})$ , 可以通过这部分数据.

乱搞 二分答案 $+$ 搜索. 具体是这样的：

不妨定义每个集合中 $a \leq b$ , 那么最优解肯定就是全选 $a$ 了. 接下来既然都选择了 $a$ , 每个集合都只剩下了 $0, b-a, b$ . 我们要求第 $k$ 大的值, 那么我们就二分这个第 $k$ 大的值是多少. 问题就转化成求不超过某个值的方案数. 先把 $b-a$ 从小到大排序, 直接爆搜, 顺序是先搜 $b$ , 再 $b-a$ , 再是 $0$ . 加上剪枝. 在搜索过程中, 每个叶子都对应一个可行解, 所以搜到的叶子数量是小于 $2k$ 的. 时间复杂度 $\Theta (n \log{n}+k \log{k})$ , 可以通过这部分数据.

满分做法

设最小割为 $C$ , 次小割为 $C'$ , 分两种情况讨论：

1) 若 $C\subseteq C'$ , 那么一定可以找到一条最小的边 $e$ , 使得 $C'=C+\{ e \}$

2) 否则, 存在一条边 $e \in C$ 且 $e \notin C'$ , 把 $e$ 去掉做最小割, 得到次小割

如果我们枚举 $e$ , 那么最坏情况是枚举了所有边, 时间复杂度 $\Theta(m \cdot networkflow(n, m))$ , 做 $k$ 次, $Time Limit Exceed$ .

如何快速选中 $2)$ 中的 $e$ 使得次小割最小呢？

去掉 $e$ , 就是将 $e$ 的边权改成 $\infty$ . 比如这幅图：

$S$---$C_1$--->$x$---$C_2$--->$y$---$C_3$--->$T$

我们要将边 $C_2$ 强制不割, 那么就是将它改成 $\infty$ . 其实增加的流量就是 $S$ 到 $x$ 和 $y$ 到 $T$ 在残余网络上的流量, 两者取最小值就是答案. 那么我们就需要在原最小割 $C$ 中预处理从 $S$ 到 $i$ 和从 $i$ 到 $T$ 在残余网络上的流量. 时间复杂度 $\Theta (n \cdot networkflow(n, m)+m)$

求得次小割之后, 将所有方案全集 $\mathfrak{S}$ 分成两类 $\mathfrak{S}_1, \mathfrak{S}_2$ , 其中 $\mathfrak{S}_1$ 表示强制包含 $e$ , $\mathfrak{S}_2$ 表示强制不包含 $e$ .

最优解和次优解分别是 $\mathfrak{S}_1, \mathfrak{S}_2$ 中的最优解, 第三优解即 $\mathfrak{S}_1, \mathfrak{S}_2$ 的次优解中较小的一个.

继续将 $\mathfrak{S}_1, \mathfrak{S}_2$ 的一个分类, 重复 $k$ 次.

时间复杂度：$\Theta (k(n \cdot networkflow(n, m)+m))$ , 结合前面的算法, 期望得分 $100$ 分.