Score : $600$ points

问题描述

我们有一个 $H$ 行和 $W$ 列的网格。令 $(i,j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的方格。

在这个网格上，有编号为 $1$ 到 $N$ 的 $N$ 个白色棋子。第 $i$ 个棋子位于位置 $(A_i,B_i)$。

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

找出将每行和每列至少包含一个黑色棋子所需的最小总代价。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.

On this grid, there are $N$ white pieces numbered $1$ to $N$. Piece $i$ is on $(A_i,B_i)$.

You can pay the cost of $C_i$ to change Piece $i$ to a black piece.

Find the minimum total cost needed to have at least one black piece in every row and every column.

Constraints

• $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$
• All pairs $(A_i,B_i)$ are distinct.
• There is at least one white piece in every row and every column.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$H$ $W$ $N$

$A_1$ $B_1$ $C_1$

$\hspace{23pt} \vdots$

$A_N$ $B_N$ $C_N$

Output

Print the answer.

Sample Input 1

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

Sample Output 1

1110

By paying the cost of $1110$ to change Pieces $2, 3, 4$ to black pieces, we can have a black piece in every row and every column.

Sample Input 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

Sample Output 2

2800000000

Sample Input 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

Sample Output 3

6

update @ 2024/3/10 10:05:38