给出一个有向带权网络 $G = (V, E)$,权值函数 $w: E \rightarrow \mathbb{Z^{*}}$(即任意边 $e$ 的权值 $w(e)$ 均为正整数),和点 $s, t \in E$,使得在 $G' = (V, E - S)$ 上不存在 $s$ 到 $t$ 的路径。
设 $\mathfrak{S}$ 是所有满足条件的边集 $S$ 的全集,按 $w(S)$ 从小到大输出 $\mathfrak{S}$ 中前 $k$ 小的边集的边权和。其中 $w(S) = \sum_{e \in S} w(e)$。
输入格式
第一行包含 $5$ 个正整数 $n, m, s, t, k$,其中 $s, t, k$ 意义如上,$n, m$ 分别表示 $\lvert V \rvert, \lvert E \rvert$(即点数和边数)。规定图中的节点用 $1$ 到 $n$ 的整数表示。保证 $s \neq t$。
接下来 $m$ 行,每行 $3$ 个整数 $x, y, z$,表示一条边权为 $z$ 的从 $x$ 到 $y$ 的边。可能有重边但保证没有自环。
输出格式
如果 $\lvert \mathfrak{S} \rvert < k$,先输出 $\lvert \mathfrak{S} \rvert$ 行,每行包含一个整数,表示前 $\lvert \mathfrak{S} \rvert$ 个 $w(S)$;再输出一行一个整数 $-1$。
如果 $\lvert \mathfrak{S} \rvert \geq k$,则输出 $k$ 行,表示前 $k$ 个 $w(S)$。
两种情况均需按照 $w(S)$ 从小到大输出。
样例一
input
3 3 1 3 100 1 2 3 2 3 4 1 3 5
output
8 9 12 -1
样例二
input
5 8 1 5 10 1 2 45176 1 3 41088 1 4 32001 2 5 48931 3 5 39291 4 5 28970 2 3 48131 4 2 49795
output
116468 117192 118265 120223 145438 147235 149193 157556 158280 161311
样例三
见样例数据下载。
限制与约定
测试点编号 | $n$ | $m$ | $k$ | 约束 |
---|---|---|---|---|
1 | $\leq 10$ | $\leq 20$ | $\leq 1000000$ | 边权不超过 $65536$ |
2 | ||||
3 | $\leq 50$ | $\leq 100$ | $\leq 100$ | |
4 | ||||
5 | ||||
6 | ||||
7 | $\leq 3000$ | $= 2n - 4$ | $\leq 500000$ | $s$ 有边连向所有非 $t$ 节点, 所有非 $s$ 结点有边连向 $t$, 边权不超过 $2^{31} - 1$ |
8 | ||||
9 | ||||
10 | ||||
11 | $\leq 150000$ | $\leq 500000$ | ||
12 | ||||
13 | ||||
14 | ||||
15 | $\leq 50$ | $\leq 1500$ | $\leq 100$ | 边权不超过 $65536$ |
16 | ||||
17 | ||||
18 | ||||
19 | ||||
20 |
时间限制:$2\texttt{s}$
空间限制:$256\texttt{MB}$