Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What is going on with this article?
@Kept1994

[競プロ用]最小全域木まとめ

最小全域木を求める手法

  • プリム法
  • クラスカル法

使い分け

議論になっていた
https://togetter.com/li/776049

入力形式で使い分ける?

  • ノード間のコストが行列で渡される → プリム法
  • 2点のノードとそのコストの組み合わせで渡される。 → クラスカル法

プリム法

  1. 任意のスタート地点から始める。
  2. 移動可能なノードのうち最も低コストで移動できるものを選び繋ぐ。
  3. 2を繰り返し、全てのノードを繋いだ時点で最小全域木となる。

どうすればいいか

ノードを繋ぐ度に選択肢が広がっていき、常にその中で最小のものを選択したい。
→ 優先度付きキュー(heapq)を用いる。

heapqにタプルを渡すと一番目の要素で最小値を判断されることを利用する。

何がいいのか

O(ElogV)。
フィボナッチヒープを使うとより早い?

イメージ

使用例

AOJ ALDS1_12_A

プリム法
import heapq

def main():
    n = int(input())
    next = []   # 隣接管理のリスト
    for _ in range(n):
        l = list(map(int, input().split()))
        next.append([(c, i) for i, c in enumerate(l) if c != -1])
    visited = [0] * n
    connection = 0
    q = [(0, 0)]    # (cost, v)
    heapq.heapify(q)
    ans = 0
    while len(q):
        cost, v = heapq.heappop(q)
        if visited[v]:
            continue

        # そのノードと繋げる
        visited[v] = 1
        connection += 1
        ans += cost

        # 新たに繋げたノードから行けるところをエンキュー
        for i in next[v]:
            heapq.heappush(q, i)

        # 全部のノードが繋がったら終了
        if connection == n:
            break
    print(ans)
    return

クラスカル法

  1. 全ての辺を重みの小さいものから順に選びとっていく。
  2. その過程で閉路を作ってしまうものは捨てる。全ての辺に対してこれを行う。
  3. 最終的に選び取った辺のみで最小全域木となる。

どうすればいいか

1 → 辺のコストを元にソートする。リストの各要素をタプルにしてソートすると1番目の要素でソートされるテクニックを利用。
2 → 「閉路ができる」=「既に2点が繋がっているところに辺を作る」なのでUnionFind木で確認する。

何がいいのか

O(ElogV)。

イメージ

使用例

AOJ GRL_2_A

クラスカル法
def main():
    V, E = map(int, input().split())
    uf = UnionFind(V)

    # 1の過程
    edges = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        edges.append((w, s, t))
    edges.sort()

    # 2の過程
    cost = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            cost += w
            uf.union(s, t)
    print(cost)
    return

追記(6/1)

考えること

  • 辺の数が膨大になるとO(ElogV)のオーダーでは間に合わないので、非常に辺が多い場合には候補となる辺を減らさないかを考えるのが有力。 → 応用例参照
  • 最小全域木のこれらの手法は多重辺があっても使用できる。→ 同じコストの辺を重複してカウントしても問題ない

応用例

ARC076 D - Built?
1つめ:Eが膨大なケースでは予め減らすことを検討する。
→今回はx座標上でもy座標上でも隣接しない町同士は選ばれないことを利用。
2つめ:x軸、y軸ともに隣接する町に該当する場合には2回カウントされるが気にしない。

def main():
    N = int(input())
    nodes = []
    for i in range(N):
        x, y = map(int, input().split())
        nodes.append((x, y, i))  # 座標に一意性があればタプルのままUnionFindにぶっこめるが、同一座標に町があるケースがあるのでナンバリングする。

    uf = UnionFind(N)
    nodes_sorted_by_x = sorted(nodes)
    nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])

    edges = []
    for i in range(N - 1):
        dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
        dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_x[i][2],  nodes_sorted_by_x[i + 1][2]))

    for i in range(N - 1):
        dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
        dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_y[i][2],  nodes_sorted_by_y[i + 1][2]))

    edges.sort()

    ans = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            ans += w
            uf.union(s, t)
    print(ans)

Appendix

タプルのリストをソートする際のキーを指定する。

# 通常はタプルの1番目の要素でソートされる。
sortedByFirstKey  = sorted(listOfTuple)
# Keyにラムダ式を指定し、タプルの2つ目の要素でソートするようにする。
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1])
# reverse
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1], reverse=True)

特に辞書のリストをソートしようとするとエラーするので上記のようにkeyを指定してあげる必要がある。
reverseで逆順を指定する。sort()でもsorted()でも使用可能。


参考

4
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Kept1994
社会人3年目のインフラエンジニア兼薬剤師。AWSを用いた開発業務中。基本Inputオタクなので使わない知識が自然淘汰されていく前にOutputして定着を図りたい。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
4
Help us understand the problem. What is going on with this article?