Day 012-Q2 — Phase 7 総復習（複合問題）

問題

重み付き有向グラフ G（頂点数 N、辺数 M）が与えられる。頂点 0 を根とする最小全域有向木（最小費用の入来木）を求め、総コストを出力。見つからない場合は -1。さらに Q 個のクエリ (u, v, x) は「辺 (u→v) のコストを x に変更」、変更後の最小有向全域木の総コストを答えよ（変更は永続）。

制約

入出力例

4 5
0 1 3
0 2 5
1 2 1
1 3 4
2 3 2
1
1 2 10

9
18

ヒント (段階的開示)

def mdst(n, root, edges):
    while True:
        # 各頂点の最小入来辺
        min_in = [INF] * n
        for w, u, v in edges:
            if v != root and w < min_in[v]:
                min_in[v] = w
        # サイクル検出 → 縮約 → 再帰
        ...

模範解答 (Python)

📋 コピーimport sys
from collections import defaultdict
input = sys.stdin.readline

def mdst(n, root, edges):
    INF = float('inf')
    while True:
        min_in = [INF] * n
        min_from = [-1] * n
        for w, u, v in edges:
            if v != root and w < min_in[v]:
                min_in[v], min_from[v] = w, u
        for v in range(n):
            if v != root and min_in[v] == INF:
                return -1
        visited = [-1] * n
        comp = [-1] * n
        cycle_id = 0
        for s in range(n):
            v = s
            while v != root and visited[v] == -1:
                visited[v] = s
                v = min_from[v]
            if v != root and visited[v] == s:
                u = v
                while comp[u] == -1:
                    comp[u] = cycle_id
                    u = min_from[u]
                cycle_id += 1
        if cycle_id == 0:
            return sum(min_in[v] for v in range(n) if v != root)
        for v in range(n):
            if comp[v] == -1:
                comp[v] = cycle_id
                cycle_id += 1
        new_edges = []
        for w, u, v in edges:
            nu, nv = comp[u], comp[v]
            if nu != nv:
                new_edges.append((w - min_in[v], nu, nv))
        root = comp[root]
        n = cycle_id
        edges = new_edges

def solve():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        edges.append([w, u, v])
    print(mdst(N, 0, [list(e) for e in edges]))
    Q = int(input())
    for _ in range(Q):
        u, v, x = map(int, input().split())
        for e in edges:
            if e[1] == u and e[2] == v:
                e[0] = x
                break
        print(mdst(N, 0, [list(e) for e in edges]))

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 重複辺・自己ループ対応
• Phase 8: 競技数学へ

自己評価

自分の回答

気づき・メモ