AT_abc352_e.[ABC352E] Clique Connect

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

有一个包含 $N$ 个顶点的带权无向图 $G$ 。 $G$ 的每个顶点编号为 $1$ 到 $N$ 。最开始， $G$ 中没有任何边。

现在要进行 $M$ 次操作，每次操作会向 $G$ 中添加一些边。第 $i$ 次操作如下：

给定一个包含 $K_i$ 个顶点的顶点子集 $S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace$ 。对于所有满足 $u,v\in S_i$ 且 $u < v$ 的 $u,v$ ，在顶点 $u$ 和顶点 $v$ 之间添加一条权值为 $C_i$ 的边。

请判断在进行完 $M$ 次操作后， $G$ 是否连通。如果连通，请输出 $G$ 的最小生成树中所有边的权值之和；如果不连通，输出 $-1$ 。

输入格式

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

$N$ $M$ $K_1$ $C_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,K_1}$ $K_2$ $C_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,K_2}$ $\vdots$ $K_M$ $C_M$ $A_{M,1}$ $A_{M,2}$ $\dots$ $A_{M,K_M}$

输出格式

如果在进行完 $M$ 次操作后 $G$ 不连通，输出 -1；如果连通，输出 $G$ 的最小生成树中所有边的权值之和。

输入输出样例

输入#1
```
4 3
3 3
1 2 3
2 2
1 2
3 4
1 3 4
```
输出#1
```
9
```
输入#2
```
3 2
2 1
1 2
2 1
1 2
```
输出#2
```
-1
```

输入#3

10 5
6 158260522
1 3 6 8 9 10
10 877914575
1 2 3 4 5 6 7 8 9 10
4 602436426
2 6 7 9
6 24979445
2 3 4 5 8 10
4 861648772
2 4 8 9

输出#3

1202115217

说明/提示

限制条件

$2\leq N \leq 2\times 10^5$
$1\leq M \leq 2\times 10^5$
$2\leq K_i \leq N$
$\displaystyle\sum_{i=1}^{M} K_i \leq 4\times 10^5$
$1\leq A_{i,1} < A_{i,2} < \dots < A_{i,K_i} \leq N$
$1\leq C_i \leq 10^9$
所有输入均为整数

样例解释 1

左图是进行完 $M$ 次操作后的 $G$ ，右图是其最小生成树之一（边上的数字表示该边的权值）。最小生成树中所有边的权值之和为 $3+2+4=9$ 。

样例解释 2

即使进行了 $M$ 次操作， $G$ 依然不连通。

由 ChatGPT 4.1 翻译

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

首页