プリム法の応用1 Bash(Beta)編（paizaランク S 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

連結成分 1、頂点数 N、重み付き、自己ループなしの無向グラフ G が隣接行列の形で与えられます。

N 個の頂点は K 個のグループに分けられます。各グループには最低でも 1 つの頂点が含まれます。

1 つのグループを G から除外して最小全域木の辺の重みの総和が最小になる時の、除外されるグループのインデックスを出力してください。

条件を満たすグループが複数ある場合、インデックスが小さい方のグループのインデックスを出力してください。

なお、どのグループを除外してもグラフは連結であることが保証されています。

入力される値

・G の頂点数 N

・総グループ数 K

・i 個目のグループに属する頂点数 K_i (1 ≦ i ≦ K)

・i 個目のグループに属する各頂点 G_i (1 ≦ G_i ≦ K_i)

・G の各辺間の重み C_{i,j} (1 ≦ i, j ≦ N)

・C_{i,j} は頂点間の辺の重みであり、隣接していない場合は 0 が与えられます。

N K
K_1
G_1 G_2 ... G_{K_1}
K_2
G_1 G_2 ... G_{K_2}
...
K_K
G_1 G_2 ... G_{K_K}
C_{1,1} C_{1,2} ... C_{1,N}
C_{2,1} C_{2,2} ... C_{2,N}
...
C_{N,1} C_{N,2} ... C_{N,N}

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

G から K-1 個のグループを選んで最小全域木の辺の重みの総和が最小になる時の、除外されるグループのインデックスを 1 行で出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 2 ≦ N ≦ 1000

・ 2 ≦ K ≦ 10

・ 1 ≦ i, j ≦ N

・ 1 ≦ k_i ≦ N-1

・ 1 ≦ G_{k_i} ≦ N

・ 1 ≦ C_{i,j} ≦ 100 または C_{i,j} = 0

入力例1: 5 2
1
1
2
3 4
0 4 5 0 0
4 0 0 0 1
5 0 0 4 3
0 0 4 0 2
0 1 3 2 0

出力例1: 2

入力例2: 7 3
3
2 4 6
2
1 5
3
2 3 5
0 0 0 4 0 1 3
0 0 2 2 0 0 0
0 2 0 0 4 4 0
4 2 0 0 6 3 0
0 0 4 6 0 0 5
1 0 4 3 0 0 2
3 0 0 0 5 2 0

出力例2: 3

問題一覧へ戻る