AT_abc231_h [ABC231H] Minimum Coloring

题目描述

有一个 $H$ 行 $W$ 列的网格。自上而下第 $i$ 行，自左而右第 $j$ 列的格子记作格子 $(i,j)$。

在网格上放置了 $N$ 个编号为 $1$ 到 $N$ 的白色棋子。棋子 $i$ 放在格子 $(A_i,B_i)$。

你可以支付 $C_i$ 的代价，将棋子 $i$ 变为黑色棋子。

请你求出，使得每一行和每一列至少有一个黑色棋子的状态下，所需支付的总代价的最小值。

输入格式

输入以如下格式从标准输入读入。

$H$ $W$ $N$
$A_1$ $B_1$ $C_1$
$\hspace{23pt}\ \vdots$
$A_N$ $B_N$ $C_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

1110

输入输出样例 #2

输入 #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 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

说明/提示

限制条件

• $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)$ 互不相同
• 每一行、每一列都至少有一个白色棋子
• 输入中所有值均为整数

样例解释 1

支付 $1110$ 的代价，将棋子 $2,3,4$ 变为黑色棋子后，可以使得每一行和每一列都至少有一个黑色棋子。

由 ChatGPT 4.1 翻译