H - Minimum Coloring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

H 行 W 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。

グリッド上には 1 から N の番号がついた N 個の白い駒が置かれています。駒 i が置かれているマスは (A_i,B_i) です。

あなたはコストを C_i 払うことで、駒 i を黒い駒に変えることができます。

どの行どの列にも黒い駒が 1 個以上ある状態にするために必要なコストの和の最小値を求めてください。

制約

  • 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 個以上の白い駒が置かれている
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

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

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