当前没有测试数据。

H - 最小上色

得分：600分

问题描述

我们有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从左上角顺时针数第 $i$ 行、第 $j$ 列的方格。

在这个网格上，有 $N$ 个白色方块，编号为 $1$ 到 $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$

输出

输出答案。

2 3 6
1 1 1
1 2 10
1 3 100
2 1 1000
2 2 10000
2 3 100000

1110

通过支付花费 $1110$ 将第 $2$、$3$、$4$ 个方块变为黑色，我们可以使每一行和每一列都有黑色方块。

1 7 7
1 2 200000000
1 7 700000000
1 4 400000000
1 3 300000000
1 6 600000000
1 5 500000000
1 1 100000000

2800000000

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

6