← 返回题目列表

AtCoder · abc352_e

H. 派系连接

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

给你一个加权无向图 G 与 N 顶点,编号 1 to N。最初, G 没有边缘。

您将执行 M 添加边缘的操作 G。的 i第次操作 (1 \leq i \leq M) 如下:

  • 给你一个顶点子集 S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace 组成 K_i 顶点。 对于每对 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}

输出

If G 终究没有连接 M 操作,打印 -1。如果 G 已连接,打印最小生成树中边的总权重 G.


示例输入 1

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

示例输出 1

9

左图显示 G 毕竟 M 操作,右图显示了最小生成树 G (边缘旁边的数字表示它们的权重)。

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


示例输入 2

3 2
2 1
1 2
2 1
1 2

示例输出 2

-1

G 终究还是没有连接 M 操作。


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