102317: [AtCoder]ABC231 H - Minimum Coloring
Description
Score : $600$ points
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
Input
题意翻译
[芷萱姐姐](https://www.luogu.com.cn/user/208653)有一个 $H \times W$ 的网格图，初始所有点都是白色的。 有 $N$ 个点可以被改变成黑色，这 $N$ 个点的坐标是 $a_i,b_i$，改变颜色的代价是 $c_i$。 你需要找到最小代价使得每行每列都至少有一个黑色节点。 数据保证有解。 Tanslated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)Output
分数：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$
输出
打印答案。
样例输入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