概要

この問題は、送電ネットワークにおける電力の流れを表すグラフ上で、発電所が順次故障する際に、すべての工場が必要電力を得られるかを判定するものです。これは典型的な最大流問題としてモデル化できます。

考察

この問題では、工場が必要とする電力量を「需要」、発電所が供給できる電力量を「供給能力」と見なし、送電線を容量付きの辺と考えると、全体をネットワークフローとして扱うことができます。

重要な観察

• 工場は最低限の電力を受け取る必要がある → 流入量の下限あり
• 発電所は供給できる上限がある → 流出量の上限あり
• 電力の保存則（流入＝流出）が各ノードで成立

このような条件を扱うには、最大流問題に帰着させるのが効果的です。

素朴なアプローチの問題点

単純に各イベントごとにグラフを作り直して流せるか試すだけでも解けますが、毎回最大流を計算するには時間がかかりすぎます。しかし、今回は最大流アルゴリズムを使えば十分高速に求められます。

解決策

各イベントで故障する発電所を非アクティブに設定し、残りの発電所を使って最大流を求め、それが全工場の需要の合計以上であれば Yes、そうでなければ No と判定します。

アルゴリズム

この問題は Dinic 法による最大流アルゴリズム を用いることで効率的に解けます。

モデリング手順

1. グラフのノードを以下のように設定：

   • ノード \(0\) ～ \(N-1\)：工場
   • ノード \(N\) ～ \(N+K-1\)：発電所
   • ノード \(N+K\)：スーパーソース（供給元のまとめ）
   • ノード \(N+K+1\)：スーパーシンク（需要先のまとめ）

2. エッジの張り方：

   • スーパーソース → 各有効な発電所：容量 \(W_k\)
   • 各工場 → スーパーシンク：容量 \(B_i\)
   • 送電線（無向）→ 双方向に容量 \(C_j\) のエッジ

3. 各イベントで故障した発電所を無効化し、再度最大流を求める。

4. 最大流が全需要（\(\sum B_i\)）以上なら Yes、そうでなければ No。

計算量

• Dinic 法の時間計算量は一般的に \(O(V^2 E)\) です（\(V\): 頂点数, \(E\): 辺数）。

• この問題では頂点数は最大でも \(N + K + 2 \leq 66\)、辺数は最大でも数百程度なので、十分高速に動作します。

• 各クエリごとに最大流を再計算するので、全体での計算量は：

• 時間計算量: \(O(Q \cdot V^2 E)\)

• 空間計算量: \(O(V + E)\)

実装のポイント

• ノード番号は0-indexedで統一する（特に送電線の入力を1引く）

• 各送電線は双方向なので、2本の有向辺を追加する

• 各イベントで新しい Dinic インスタンスを作成し、最新のグラフ構造でフローを計算している

• max_flow が全需要以上かを判定する

  ソースコード

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.level = [0] * n
        self.ptr = [0] * n

    def add_edge(self, u, v, cap):
        # forward edge
        forward = [v, cap, len(self.graph[v])]
        # backward edge
        backward = [u, 0, len(self.graph[u])]
        self.graph[u].append(forward)
        self.graph[v].append(backward)

    def bfs(self, source, sink):
        self.level = [-1] * self.n
        self.level[source] = 0
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v, cap, rev_index in self.graph[u]:
                if self.level[v] == -1 and cap > 0:
                    self.level[v] = self.level[u] + 1
                    queue.append(v)
        return self.level[sink] != -1

    def dfs(self, u, sink, flow):
        if u == sink:
            return flow
        while self.ptr[u] < len(self.graph[u]):
            v, cap, rev_index = self.graph[u][self.ptr[u]]
            if self.level[v] == self.level[u] + 1 and cap > 0:
                bottleneck = self.dfs(v, sink, min(flow, cap))
                if bottleneck > 0:
                    self.graph[u][self.ptr[u]][1] -= bottleneck
                    self.graph[v][rev_index][1] += bottleneck
                    return bottleneck
            self.ptr[u] += 1
        return 0

    def max_flow(self, source, sink):
        flow = 0
        while self.bfs(source, sink):
            self.ptr = [0] * self.n
            while True:
                pushed = self.dfs(source, sink, float('inf'))
                if pushed == 0:
                    break
                flow += pushed
        return flow

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    B = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    W = [int(data[idx + i]) for i in range(K)]
    idx += K
    
    edges = []
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        c = int(data[idx]); idx += 1
        edges.append((u, v, c))
    
    Q = int(data[idx]); idx += 1
    S = [int(data[idx + i]) - 1 for i in range(Q)]
    idx += Q
    
    total_demand = sum(B)
    
    # Node indices:
    # 0 to N-1: factories
    # N to N+K-1: power plants
    # N+K: super source
    # N+K+1: super sink
    
    SOURCE = N + K
    SINK = N + K + 1
    TOTAL_NODES = N + K + 2
    
    # Initially all power plants are active
    active = [True] * K
    
    results = []
    
    for q in range(Q):
        # Disable the failing plant
        plant = S[q]
        active[plant] = False
        
        # Build the network
        dinic = Dinic(TOTAL_NODES)
        
        # Connect super source to each active power plant with capacity W[k]
        for k in range(K):
            if active[k]:
                dinic.add_edge(SOURCE, N + k, W[k])
        
        # Connect each factory to super sink with demand B[i]
        for i in range(N):
            dinic.add_edge(i, SINK, B[i])
        
        # Add transmission lines (bidirectional)
        for u, v, c in edges:
            dinic.add_edge(u, v, c)
            dinic.add_edge(v, u, c)
        
        # Compute maximum flow
        max_flow_value = dinic.max_flow(SOURCE, SINK)
        
        # Check if all demands are satisfied
        if max_flow_value >= total_demand:
            results.append("Yes")
        else:
            results.append("No")
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。