← 返回题目列表

AtCoder · abc231_h

H. 最低着色

中文机器翻译题面 查看原题

分数: 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