#P4153. [WC2015] k 小割

    ID: 1030 远端评测题 2000ms 128MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>优先队列搜索最小割WC/CTSC/集训队2015O2优化

[WC2015] k 小割

题目描述

给出一个有向带权网络 G=(V,E)G = (V, E),权值函数 w:EZw: E \rightarrow \mathbb{Z^{*}}(即任意边 ee 的权值 w(e)w(e) 均为正整数),和点 s,tEs, t \in E,使得在 G=(V,ES)G' = (V, E - S) 上不存在 sstt 的路径。

S\mathfrak{S} 是所有满足条件的边集 SS 的全集,按 w(S)w(S) 从小到大输出 S\mathfrak{S} 中前 kk 小的边集的边权和。其中 w(S)=eSw(e)w(S) = \sum_{e \in S} w(e)

输入格式

第一行包含 55 个正整数 n,m,s,t,kn, m, s, t, k,其中 s,t,ks, t, k 意义如上,n,mn, m 分别表示 V,E\lvert V \rvert, \lvert E \rvert(即点数和边数)。规定图中的节点用 11nn 的整数表示。保证 sts \neq t

接下来 mm 行,每行 33 个整数 x,y,zx, y, z,表示一条边权为 zz 的从 xxyy 的边。可能有重边但保证没有自环。

输出格式

如果 S<k\lvert \mathfrak{S} \rvert < k,先输出 S\lvert \mathfrak{S} \rvert 行,每行包含一个整数,表示前 S\lvert \mathfrak{S} \rvertw(S)w(S);再输出一行一个整数 1-1

如果 Sk\lvert \mathfrak{S} \rvert \geq k,则输出 kk 行,表示前 kkw(S)w(S)

两种情况均需按照 w(S)w(S) 从小到大输出。

3 3 1 3 100
1 2 3
2 3 4
1 3 5
8
9
12
-1
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
116468
117192
118265
120223
145438
147235
149193
157556
158280
161311

提示

对于30%测试点,N50,m<=100,k500000N \le 50, m<=100,k \le 500000,边权不超过 6553665536

对于另外40%测试点,N150000,m<=2n4,k500000N \le 150000, m<=2n-4,k \le 500000ss 有边连向所有非 tt 节点,所有非 ss 结点有边连向 tt,边权不超过 23112^{31} - 1

对于另外30%测试点,N50,m<=1500,k100N \le 50, m<=1500,k \le 100,边权不超过 6553665536