分数: 600 点
问题陈述
我们有一个网格 H 行和 W 列。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
在这个网格上,有 N 白色碎片编号 1 to N。件 i 已开启 (A_i,B_i).
您可以支付以下费用 C_i 更改件 i 变成一个黑色的棋子。
求每行每列至少有一个黑色棋子所需的最小总成本。
约束
- 1 \leq H,W \leq 10^3
- 1 \leq N \leq 10^3
- 1 \leq A_i \leq H
- 1 \leq B_i \leq W
- 1 \leq C_i \leq 10^9
- 所有对 (A_i,B_i) 是不同的。
- 每行每列至少有一个白色棋子。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W N
A_1 B_1 C_1
\hspace{23pt} \vdots
A_N B_N C_N
输出
打印答案。
示例输入 1
2 3 6 1 1 1 1 2 10 1 3 100 2 1 1000 2 2 10000 2 3 100000
示例输出 1
1110
通过支付以下费用 1110 更改件数 2, 3, 4 对于黑子,我们可以在每一行和每一列都有一个黑子。
示例输入 2
1 7 7 1 2 200000000 1 7 700000000 1 4 400000000 1 3 300000000 1 6 600000000 1 5 500000000 1 1 100000000
示例输出 2
2800000000
示例输入 3
3 3 8 3 2 1 3 1 2 2 3 1 2 2 100 2 1 100 1 3 2 1 2 100 1 1 100
示例输出 3
6