tooh’s diary

半角全角、常体敬体が入り乱れるカオス

6/21 AOJ(クラスカル法)

こんにちは。2S1の成績がとりあえず一安心できるくらいでホッとしているとーです。

学校の授業でクラスカル法をやったので復習。プリム法を勉強したのですがこっちは結構噛み砕くのが難しくかったのでまた後回し。どうやら実行時間は大して変わらないっぽい?

クラスカル法もプリム法も、最小全域木、つまり全ての島を最も少ないコストで結ぶような木を実現するのに必要なコストを求めるためのアルゴリズムです。

クラスカル法の流れは、

①とりあえず、[コスト(距離),出発点の島,終着点の島]という辺のデータを、距離の短い順にソート
②n個の島0~n-1に対して、UF木を作っておく
③コストの短い辺から順番につなげていく。その際、出発点と終着点が同じ木に属していないことをUF木を用いて判定し、同じ木に属していれば辺で結ぶことはしない

という感じです。③については、同じ木に属しているのであれば、わざわざその辺で結ばなくとも迂回路が存在するため、このようなことになる。

練習問題↓
judge.u-aizu.ac.jp

コードはこんな感じ。

n = int(input()) #島はn*nの形式で与えられる
T = [] #ここにコストや出発、終着点の情報が入る
ans = 0 #ここに答え(最小コスト)が入る
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(n):
        if L[j] != -1:
            T.append([L[j],i,j]) #島は0からスタート
T.sort() #辺のコストの小さい順にソート

#Union Find
rank = [0]*n
par = []
for i in range(n):
    par.append(i)
def find(x,par):
    if x == par[x]:
        return par[x]
    else:
        return find(par[x],par)
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1


for i in range(len(T)):
    if find(T[i][1],par) != find(T[i][2],par):
        ans += T[i][0]
        unite(T[i][1],T[i][2],par,rank)
print(ans)