#2803. 「CCC 2018」最大战略储备

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mingqi_H

题目描述

题目译自 CCC 2018 S5. Maximum Strategic Savings

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

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

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

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

输入格式

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

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

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

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

输出格式

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

样例

样例 1 输入

2 2 1 2
1 2 1
2 1 1
2 1 1

样例 1 输出

3

样例 2 输入

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

样例 2 输出

41

样例 2 解释

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

数据范围与提示

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

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

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

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