P4153 [WC2015] k 小割

给出一个有向带权网络 $G = (V, E)$，权值函数 $w: E \rightarrow \mathbb{Z^{*}}$（即任意边 $e$ 的权值 $w(e)$ 均为正整数），和点 $s, t \in V$，使得在 $G' = (V, E - S)$ 上不存在 $s$ 到 $t$ 的路径。 设 $\mathfrak{S}$ 是所有满足条件的边集 $S$ 的全集，按 $w(S)$ 从小到大输出 $\mathfrak{S}$ 中前 $k$ 小的边集的边权和。其中 $w(S) = \sum_{e \in S} w(e)$。

无

无

| 测试点编号 | $n \le$ | $m$ | $k \le$ | 约束 | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 2$ | $10$ | $\le 20$ | ${10}^6$ | 边权不超过 $65536$ | | $3 \sim 6$ | $50$ | $\le 100$ | $100$ | 边权不超过 $65536$ | | $7 \sim 10$ | $3000$ | $= 2 n - 4$ | $5 \times {10}^5$ | $s$ 有边连向所有非 $t$ 节点，所有非 $s$ 结点有边连向 $t$，边权不超过 $2^{31} - 1$ | | $11 \sim 14$ | $1.5 \times {10}^5$ | $= 2 n - 4$ | $5 \times {10}^5$ | $s$ 有边连向所有非 $t$ 节点，所有非 $s$ 结点有边连向 $t$，边权不超过 $2^{31} - 1$ | | $15 \sim 20$ | $50$ | $\le 1500$ | $100$ | 边权不超过 $65536$ |