题目详情题解（0）讨论（0）提交记录（0）

AT_abc231_h.[ABC231H] Minimum Coloring

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 HH 行 WW 列的网格。自上而下第 ii 行，自左而右第 jj 列的格子记作格子 (i,j)(i,j)。

在网格上放置了 NN 个编号为 11 到 NN 的白色棋子。棋子 ii 放在格子 (Ai,Bi)(A_i,B_i)。

你可以支付 CiC_i 的代价，将棋子 ii 变为黑色棋子。

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

输入格式

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

HH WW NN
A1A_1 B1B_1 C1C_1
 ⋮\hspace{23pt}\ \vdots
ANA_N BNB_N CNC_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

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

说明/提示

限制条件

  • 1≤H,W≤1031 \leq H,W \leq 10^3
  • 1≤N≤1031 \leq N \leq 10^3
  • 1≤Ai≤H1 \leq A_i \leq H
  • 1≤Bi≤W1 \leq B_i \leq W
  • 1≤Ci≤1091 \leq C_i \leq 10^9
  • (Ai,Bi)(A_i,B_i) 互不相同
  • 每一行、每一列都至少有一个白色棋子
  • 输入中所有值均为整数

样例解释 1

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页