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

AT_abc364_f.[ABC364F] Range Connect MST

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

有一个包含 N+QN+Q 个顶点的图，顶点编号为 1,2,…,N+Q1, 2, \ldots, N+Q。初始时图中没有任何边。

对于该图，依次进行 i=1,2,…,Qi=1,2,\ldots,Q 的如下操作：

  • 对于每个满足 Li≤j≤RiL_i \leq j \leq R_i 的整数 jj，在顶点 N+iN+i 与顶点 jj 之间添加一条无向边，边的代价为 CiC_i。

所有操作结束后，请判断该图是否连通。如果连通，请求出该图的最小生成树的总代价。

其中，最小生成树指的是所有顶点连通且边权和最小的生成树。

输入格式

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

NN QQ
L1L_1 R1R_1 C1C_1
L2L_2 R2R_2 C2C_2
⋮\vdots
LQL_Q RQR_Q CQC_Q

输出格式

如果图是连通的，输出最小生成树的总代价。否则输出 −1-1。

输入输出样例

  • 输入#1

    4 3
1 2 2
1 3 4
2 4 5

    输出#1

    22

  • 输入#2

    6 2
1 2 10
4 6 10

    输出#2

    -1

  • 输入#3

    200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

    输出#3

    199651870599998

说明/提示

限制条件

  • 1≤N,Q≤2×1051 \leq N, Q \leq 2 \times 10^5
  • 1≤Li≤Ri≤N1 \leq L_i \leq R_i \leq N
  • 1≤Ci≤1091 \leq C_i \leq 10^9
  • 所有输入的值均为整数

样例解释 1

以下这些边构成了一个最小生成树：

  • 顶点 11 与 55 之间的代价为 22 的边
  • 顶点 22 与 55 之间的代价为 22 的边
  • 顶点 11 与 66 之间的代价为 44 的边
  • 顶点 33 与 66 之间的代价为 44 的边
  • 顶点 33 与 77 之间的代价为 55 的边
  • 顶点 44 与 77 之间的代价为 55 的边

2+2+4+4+5+5=222+2+4+4+5+5=22，因此输出 2222。

样例解释 2

该图是不连通的。

由 ChatGPT 4.1 翻译

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

首页