P4153 [WC2015] k-Min Cut

Given a directed weighted network $G = (V, E)$, a weight function $w: E \rightarrow \mathbb{Z^{*}}$ (i.e., for any edge $e$, the weight $w(e)$ is a positive integer), and vertices $s, t \in V$. Consider any edge set $S \subseteq E$, and let $G' = (V, E - S)$. If there is no path from $s$ to $t$ in $G'$, then $S$ is valid. Let $\mathfrak{S}$ be the set of all such edge sets $S$. Output the sums of edge weights of the smallest $k$ sets in $\mathfrak{S}$ by nondecreasing $w(S)$, where $w(S) = \sum_{e \in S} w(e)$.

The first line contains $5$ positive integers $n, m, s, t, k$, where $s, t, k$ are as above, and $n, m$ denote $\lvert V \rvert, \lvert E \rvert$ (the numbers of vertices and edges). Vertices are labeled from $1$ to $n$. It is guaranteed that $s \neq t$. The next $m$ lines each contain $3$ integers $x, y, z$, representing a directed edge from $x$ to $y$ with weight $z$. Multiple edges may exist, but there are no self-loops.

If $\lvert \mathfrak{S} \rvert < k$, first output $\lvert \mathfrak{S} \rvert$ lines, each containing one integer, which are the first $\lvert \mathfrak{S} \rvert$ values of $w(S)$. Then output one more line with a single integer $-1$. If $\lvert \mathfrak{S} \rvert \geq k$, output $k$ lines, which are the first $k$ values of $w(S)$. In both cases, the outputs must be in nondecreasing order of $w(S)$.

| Test Point ID | $n \le$ | $m$ | $k \le$ | Constraints | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 2$ | $10$ | $\le 20$ | ${10}^6$ | Edge weights do not exceed $65536$. | | $3 \sim 6$ | $50$ | $\le 100$ | $100$ | Edge weights do not exceed $65536$. | | $7 \sim 10$ | $3000$ | $= 2 n - 4$ | $5 \times {10}^5$ | $s$ has edges to all vertices other than $t$; every vertex other than $s$ has an edge to $t$; edge weights do not exceed $2^{31} - 1$. | | $11 \sim 14$ | $1.5 \times {10}^5$ | $= 2 n - 4$ | $5 \times {10}^5$ | $s$ has edges to all vertices other than $t$; every vertex other than $s$ has an edge to $t$; edge weights do not exceed $2^{31} - 1$. | | $15 \sim 20$ | $50$ | $\le 1500$ | $100$ | Edge weights do not exceed $65536$. | Translated by ChatGPT 5