最小有向全域木
(Graph/SpanningTree/directed_mst.py)

• View this file on GitHub
• Last update: 2021-01-14 12:29:07+09:00

概要

最小有向全域木とその総コストを求める。

使い方

directed_mst(n: int, edges: Sequence[Tuple[int, int, int]], root: int)　-> Tuple[int, List[int]]
重み付き有向辺のリスト edges に対して、root を根とした最小有向全域木の総コスト、その有向木を表す親頂点の配列を返す。計算量 $O(E\log V)$

Depends on

• 併合可能ヒープ (Skew Heap) (DataStructure/Heap/SkewHeap.py)
• Union Find (DataStructure/UnionFind/UnionFind.py)

Verified with

• TestCase/AOJ/GRL_2_B.test.py
• TestCase/LibraryChecker/directedmst.test.py

Code

from DataStructure.UnionFind.UnionFind import UnionFind
from DataStructure.Heap.SkewHeap import SkewHeap


def directed_mst(n, edges, root):
    OFFSET = m = len(edges)
    from_ = [0] * n
    from_cost = [0] * n
    from_heap = [SkewHeap() for i in range(n)]

    uf = UnionFind(n)
    par_e = [-1] * m
    stem = [-1] * n
    used = [0] * n
    used[root] = 2
    idxs = []

    for idx, (fr, to, cost) in enumerate(edges):
        from_heap[to].push(cost * OFFSET + idx)

    res = 0
    for v in range(n):
        if used[v] != 0:
            continue
        processing = []
        chi_e = []
        cycle = 0
        while used[v] != 2:
            used[v] = 1
            processing.append(v)
            if from_heap[v].empty():
                return -1, [-1] * n
            from_cost[v], idx = divmod(from_heap[v].pop(), OFFSET)
            from_[v] = uf.root(edges[idx][0])
            if stem[v] == -1:
                stem[v] = idx
            if from_[v] == v:
                continue
            res += from_cost[v]
            idxs.append(idx)
            while cycle:
                par_e[chi_e.pop()] = idx
                cycle -= 1
            chi_e.append(idx)
            if used[from_[v]] == 1:
                p = v
                while True:
                    if not from_heap[p].empty():
                        from_heap[p].add(-from_cost[p] * OFFSET)
                    if p != v:
                        uf.merge(v, p)
                        from_heap[v].meld(from_heap[p])
                    p = uf.root(from_[p])
                    new_v = uf.root(v)
                    from_heap[new_v] = from_heap[v]
                    v = new_v
                    cycle += 1
                    if p == v:
                        break
            else:
                v = from_[v]
        for v in processing:
            used[v] = 2

    used_e = [False] * m
    par = [-1] * n
    for idx in reversed(idxs):
        if used_e[idx]:
            continue
        fr, to, cost = edges[idx]
        par[to] = fr
        x = stem[to]
        while x != idx:
            used_e[x] = True
            x = par_e[x]
    return res, par

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page