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

AT_arc212_b.[ARC212B] Stones on Grid

普及/提高-

通过率：0%

AC君温馨提醒

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

题目描述

有一个 NN 行 NN 列的方格。第 ii 行从上数、第 jj 列从左数的格子被称作 (i,j)(i,j)。

你需要依次进行 i=1,2,…,Mi=1,2,\ldots,M 次如下操作：

  • 操作 ii：选择是否在格子 (xi,yi)(x_i, y_i) 上放置一颗石子。如果选择放置石子，则需要支付 cic_i 的花费；否则不花费任何费用。

但是，你必须在第 1 次操作中放一颗石子。

请判断是否能够实现以下目标，如果可以，请求出最小的总花费。

  • 目标：对于每个 i (1≤i≤N)i\ (1 \leq i \leq N)，第 ii 行所放石子的数量恰好等于第 ii 列所放石子的数量。

输入格式

输入由标准输入给出，格式如下：

N MN\ M
x1 y1 c1x_1\ y_1\ c_1
x2 y2 c2x_2\ y_2\ c_2
⋮\vdots
xM yM cMx_M\ y_M\ c_M

输出格式

如果无法达成目标，输出 -1。如果可以，请输出实现目标的最小总花费。

输入输出样例

  • 输入#1

    4 5
2 4 5
4 1 2
2 1 3
3 3 9
1 2 4

    输出#1

    11

  • 输入#2

    3 3
1 1 1000000000
2 2 100000000
3 3 10000000

    输出#2

    1000000000

  • 输入#3

    2 1
1 2 10

    输出#3

    -1

说明/提示

样例解释1

可以通过在第 1、2、5 次操作中各放一个石子来达成目标。

此时总花费为 5+2+4=115+2+4=11。为了实现目标，无法做到比 1111 更少，因此输出为 1111。

样例解释2

你必须在第 1 次操作中放一颗石子。

题目约束

  • 1≤N,M≤2×1051 \le N, M \le 2 \times 10^5
  • 1≤xi,yi≤N1 \le x_i, y_i \le N
  • 1≤ci≤1091 \le c_i \le 10^9
  • (xi,yi)(x_i, y_i) 两两不同。
  • 所有输入均为整数。

由 ChatGPT 5 翻译

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

首页