J - 連結
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
Problem Statement
N 個の頂点からなるグラフがある。頂点は 1,\ 2,\ ...,\ N と番号が振られている。i (1\leq i\leq N) 番目の頂点は非負整数の重み a_i をもつ。
はじめ、グラフには辺がない。あなたはグラフに無向辺を追加していくことができる。グラフに追加できる辺の候補は M 本ある。辺は 1,\ 2,\ ...,\ M と番号が振られている。i (1\leq i\leq M) 番目の辺は、頂点 x_i と y_i を端点とし、非負整数の重み z_i をもつ。
あなたの目標は、すべての頂点を連結にすることである。そのために、まだグラフに追加していない辺のうちちょうど 1 本を選んでグラフに追加する、という操作を任意の回数行うことができる。ただし、どの瞬間においても次の条件が成り立っていなければならない。
- グラフのどの連結成分についても、(頂点の重みの総和)\geq(辺の重みの総和) である。
すべての頂点を連結にできるか判定せよ。できるならば、グラフに辺を追加していく方法を一つ出力せよ。
Constraints
- 2\leq N\leq10^5
- a_i は整数,0\leq a_i\leq10^9
- 1\leq M\leq10^5
- 1\leq x_i<y_i\leq N
- z_i は整数,0\leq z_i\leq10^9
Input Format
入力は以下の形式で標準入力から与えられる。
N M a_1 a_2 ... a_N x_1 y_1 z_1 x_2 y_2 z_2 : x_M y_M z_M
Output Format
すべての頂点を連結にできないならば、-1
とだけ一行に出力せよ。
すべての頂点を連結にできるならば、グラフに辺を追加していく方法を一つ次のように出力せよ。
- 1 行目には、グラフに追加する辺の本数 m (1\leq m\leq M) を出力せよ。
- 2 行目からの m 行のうち k 行目には、k 番目にグラフに追加する辺の番号 i_k (1\leq i_k\leq M) を出力せよ。
Sample Input 1
4 3 50 0 0 50 1 2 0 2 3 100 3 4 0
Sample Output 1
3 1 3 2
2 番目の辺を追加するのは最後でなければならない。
Sample Input 2
2 3 50 50 1 2 100 1 2 101 1 2 102
Sample Output 2
1 1
多重辺が含まれている。
Sample Input 3
3 1 50 50 50 1 2 100
Sample Output 3
-1
すべての辺をグラフに追加しても、すべての頂点を連結にできない。