103524: [Atcoder]ABC352 E - Clique Connect

Problem Statement

You are given a weighted undirected graph $G$ with $N$ vertices, numbered $1$ to $N$. Initially, $G$ has no edges.

You will perform $M$ operations to add edges to $G$. The $i$-th operation $(1 \leq i \leq M)$ is as follows:

• You are given a subset of vertices $S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace$ consisting of $K_i$ vertices. For every pair $u, v$ such that $u, v \in S_i$ and $u < v$, add an edge between vertices $u$ and $v$ with weight $C_i$.

After performing all $M$ operations, determine whether $G$ is connected. If it is, find the total weight of the edges in a minimum spanning tree of $G$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $2 \leq K_i \leq N$
• $\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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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}$

Output

If $G$ is not connected after all $M$ operations, print -1. If $G$ is connected, print the total weight of the edges in a minimum spanning tree of $G$.

Sample Input 1

4 3
3 3
1 2 3
2 2
1 2
3 4
1 3 4

Sample Output 1

9

The left diagram shows $G$ after all $M$ operations, and the right diagram shows a minimum spanning tree of $G$ (the numbers next to the edges indicate their weights).

The total weight of the edges in the minimum spanning tree is $3 + 2 + 4 = 9$.

Sample Input 2

3 2
2 1
1 2
2 1
1 2

Sample Output 2

-1

$G$ is not connected even after all $M$ operations.

Sample Input 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

Sample Output 3

1202115217

问题描述

你被给定一个有 $N$ 个顶点（编号为 $1$ 到 $N$）的加权无向图 $G$，初始时，$G$ 没有任何边。

你将执行 $M$ 个操作来向 $G$ 添加边。第 $i$ 个操作 $(1 \leq i \leq M)$ 如下：

• 你会得到一个包含 $K_i$ 个顶点的子集 $S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace$。 对于每一对 $u, v$，如果 $u, v \in S_i$ 且 $u < v$，则在顶点 $u$ 和 $v$ 之间添加一条权重为 $C_i$ 的边。

执行完所有 $M$ 个操作后，判断 $G$ 是否连通。如果连通，找出 $G$ 的最小生成树的边总权重。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $2 \leq K_i \leq N$
• $\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$
• 所有输入值都是整数。

输入

输入数据从标准输入给出，格式如下：

$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$ 连通，打印 $G$ 的最小生成树的边总权重。

样例输入 1

4 3
3 3
1 2 3
2 2
1 2
3 4
1 3 4

样例输出 1

9

左边的图显示了所有 $M$ 操作后 $G$ 的样子，右边的图显示了 $G$ 的一个最小生成树（边旁边的数字表示边的权重）。

最小生成树的边总权重为 $3 + 2 + 4 = 9$。

样例输入 2

3 2
2 1
1 2
2 1
1 2

样例输出 2

-1

即使在所有 $M$ 操作后，$G$ 仍然不连通。

样例输入 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