#P4809. [CCC2018] 最大战略储备

[CCC2018] 最大战略储备

题目描述

题目译自 CCC 2018 S5「Maximum Strategic Savings

NN 个星球,编号为 1N1\ldots N。每个星球有 MM 座城市,编号为 1M1\ldots M。我们将 ee 星球上的城市 ff 记作 (e,f)(e,\,f)

N×PN\times P 条双向航线,对于每个星球 e(1eN)e(1\le e\le N),有 PP 条航线,编号为 11PP。第 ii 条航线连接城市 (e,ai)(e,\,a_i)(e,bi)(e,\,b_i),且每天需要花费 cic_i 的代价维护。

M×QM\times Q 个双向港口。对于所有编号为 f(1fM)f(1\le f\le M) 的城市,有 QQ 个港口,编号为 11QQ。第 jj 个港口可以连接城市 (xj,f)(x_j,\,f)(yj,f)(y_j,\,f),且每天需要花费 zjz_j 的代价维护。

现在需要拆除一些港口和(或)取消一些航线,使得城市之间仍能保持联通,且节省的代价之和最大。

输入格式

第一行四个整数,分别为 N,M,P,Q (0N,M,P,Q105)N,\,M,\,P,\,Q\ (0\le N,\,M,\,P,\,Q\le10^5)

接下来 PP 行,每行三个整数 $a_i,\,b_i,\,c_i(1\le a_i,\,b_i\le M,\,1\le c_i\le10^8)$。

再接下来 QQ 行,每行三个整数 $x_j,\,y_j,\,z_j(1\le x_j,\,y_j\le N,\,1\le z_j\le 10^8)$。

数据保证城市之间两两联通,可能有重边或自环。

输出格式

输出一行一个整数表示每天最多能节省的代价之和。

2 2 1 2
1 2 1
2 1 1
2 1 1
3
2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5
41

提示

样例 2 解释

一种可行的最优解是关闭城市 (1,1)(1,\,1)(1,1)(1,1)(2,1)(2,\,1)(2,1)(2,\,1)(1,1)(1,\,1)(1,2)(1,\,2)(1,3)(1,\,3)(1,2)(1,\,2)(2,3)(2,\,3)(2,2)(2,\,2) 之间的航线;并关闭城市 (2,3)(2,\,3)(1,3)(1,\,3) 间的港口。最终可以节省 8+8+6+7+7+5=418 + 8 + 6 + 7 + 7 + 5 = 41 的代价。

对于 215\frac{2}{15} 的数据,P,Q100P,\,Q\le100,且对于所有的 1iP1\le i\le P,都有 ci=1c_i=1;对于所有的 1jQ1\le j\le Q,都有 zj=1z_j=1

对于另外 215\frac{2}{15} 的数据,P,Q200P,\,Q\le 200

对于另外 515\frac{5}{15} 的数据,N,M200N,\,M\le 200

对于全部的数据,1N,M,P,Q1051\le N,\,M,\,P,\,Q\le10^5