Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 450 点
問題文
N 頂点からなる重み付き無向グラフ G があります。 G の各頂点には 1 から N までの番号が付けられています。 最初、G には辺が 1 本も存在しません。
今から、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\in S_i かつ u<v を満たす全ての 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
- \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
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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
左の図は M 回の操作を全て行ったあとの G を、右の図はその最小全域木の 1 つを表しています(辺の横に書かれた数はその辺の重みを示します)。
最小全域木に含まれる辺の重みの総和は 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
Score: 450 points
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