Day 013-Q5 — Phase 8 総復習（最高難度統合問題）

問題

N 都市 M 道路のネットワーク。各道路は通行コスト $w_i$ と通信帯域 $b_i$ を持つ。クエリ: (1) 最短経路, (2) 流量 k の最小コスト, (3) 最小ボトルネック全域木の最大辺重み。

制約

入出力例

4 5
1 2 3 2
1 3 1 5
2 4 4 1
3 4 2 3
2 3 2 4
4
1 1 4
2 1 4 3
2 1 4 4
3

3
9
-1
2

ヒント (段階的開示)

模範解答 (Python)

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

def solve():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w, b = map(int, input().split())
        u -= 1; v -= 1
        edges.append((u, v, w, b))
    INF = float('inf')
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for u, v, w, b in edges:
        dist[u][v] = min(dist[u][v], w)
        dist[v][u] = min(dist[v][u], w)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    parent = list(range(N))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(x, y):
        px, py = find(x), find(y)
        if px == py: return False
        parent[px] = py
        return True
    sorted_edges = sorted(edges, key=lambda e: e[2])
    mst_max = 0
    parent = list(range(N))
    for u, v, w, b in sorted_edges:
        if union(u, v):
            mst_max = max(mst_max, w)

    class MCMFGraph:
        def __init__(self, n):
            self.n = n
            self.graph = [[] for _ in range(n)]
        def add_edge(self, u, v, cap, cost):
            self.graph[u].append([v, cap, cost, len(self.graph[v])])
            self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1])
        def flow(self, s, t, max_flow):
            total_cost = total_flow = 0
            while total_flow < max_flow:
                d = [INF] * self.n
                d[s] = 0
                in_q = [False] * self.n
                pv = [-1] * self.n; pe = [-1] * self.n
                q = deque([s]); in_q[s] = True
                while q:
                    v = q.popleft(); in_q[v] = False
                    for i, (nv, cap, cost, _) in enumerate(self.graph[v]):
                        if cap > 0 and d[v] + cost < d[nv]:
                            d[nv] = d[v] + cost
                            pv[nv] = v; pe[nv] = i
                            if not in_q[nv]:
                                q.append(nv); in_q[nv] = True
                if d[t] == INF:
                    return total_flow, total_cost, False
                f = max_flow - total_flow
                v = t
                while v != s:
                    f = min(f, self.graph[pv[v]][pe[v]][1]); v = pv[v]
                v = t
                while v != s:
                    self.graph[pv[v]][pe[v]][1] -= f
                    self.graph[v][self.graph[pv[v]][pe[v]][3]][1] += f
                    v = pv[v]
                total_flow += f; total_cost += f * d[t]
            return total_flow, total_cost, True

    Q = int(input())
    results = []
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            s, t = q[1] - 1, q[2] - 1
            results.append(dist[s][t] if dist[s][t] != INF else -1)
        elif q[0] == 2:
            s, t, k = q[1] - 1, q[2] - 1, q[3]
            g = MCMFGraph(N)
            for u, v, w, b in edges:
                g.add_edge(u, v, b, w)
                g.add_edge(v, u, b, w)
            flow, cost, ok = g.flow(s, t, k)
            results.append(cost if ok and flow == k else -1)
        elif q[0] == 3:
            results.append(mst_max)
    print('\n'.join(map(str, results)))

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 動的グラフ + Link-Cut Tree

自己評価

自分の回答

気づき・メモ