分数: 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