最大全域木問題

問題

頂点数 $N$、辺数 $M$ のグラフがあります。

頂点には $1$ から $N$ までの番号が付けられており、辺 $i$ は頂点 $A_i$ と $B_i$ を双方向に結ぶ長さ $C_i$ の辺です。

このグラフの最大全域木における辺の長さの総和を求めて下さい。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq 100000 $
🔹$ 1 \leqq C_i \leqq 10000 $
🔹このグラフは連結である。

解き方

全域木とは、$M$ 個の辺の中からいくつかを選んで作った全ての頂点が繋がっている木のことです。

全域木の中でも「長さの合計」が最大となるものを最大全域木といいます。

最大全域木は『長い辺から追加していく』という単純な貪欲法によって導き出すことができます。

ソースコード解説

前回記事では最小全域木の辺の長さの総和を求めましたが、今回の最大全域木の辺の長さの総和を求める場合は、辺の長さのソート順を逆にする変更だけで対応できます。

ソースコードの50行目だけ変更しており、辺の長い順にソートしています。

その他の処理は前回記事同様ですので、処理詳細はそちらをご参照下さい。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#-------- 入力例１ ---------
N = 7       # 頂点数
M = 9       # 辺数
# つながっている２つの頂点とその長さ
edges = [
    (1, 2, 12),
    (1, 3, 10),
    (2, 6, 160),
    (2, 7, 15),
    (3, 4, 1),
    (3, 5, 4),
    (4, 5, 3),
    (4, 6, 120),
    (6, 7, 14)
]
#---------------------------
# Union-Find 木
class unionfind:
    # n 頂点の Union-Find 木を作成
    def __init__(self, n):
        self.n = n
        self.par = [ -1 ] * (n + 1) # 最初は親が無い
        self.size = [ 1 ] * (n + 1) # 最初はグループの頂点数が 1
    
    # 頂点 x の根を返す関数
    def root(self, x):
        # 1 個先（親）がなくなるまで進み続ける
        while self.par[x] != -1:
            x = self.par[x]
        return x
    
    # 要素 u, v を統合する関数
    def unite(self, u, v):
        rootu = self.root(u)
        rootv = self.root(v)
        if rootu != rootv:
            # u と v が異なるグループのときのみ処理を行う
            if self.size[rootu] < self.size[rootv]:
                self.par[rootu] = rootv
                self.size[rootv] += self.size[rootu]
            else:
                self.par[rootv] = rootu
                self.size[rootu] += self.size[rootv]
    
    #  要素 u と v が同一のグループかどうかを返す関数
    def same(self, u, v):
        return self.root(u) == self.root(v)

# 辺を長さの大きい順にソート
edges.sort(key = lambda x: -x[2])

# 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
    if not uf.same(a, b):
        uf.unite(a, b)
        answer += c

# 答えの出力
print('解：', answer)

[実行結果（入力例１）]

解： 321

最大全域木における辺の長さの総和を求めることができました。