[CCC2018] 最大战略储备
题目描述
**题目译自 [CCC 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) S5「[Maximum Strategic Savings](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%201/seniorEF.pdf)」**
有 $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$。