概要

複数の発電所と工場が送電線で結ばれたネットワークにおいて、発電所が順番に故障していく中、すべての工場に必要な電力を供給し続けられるかを各段階で判定する問題です。

考察

複数の供給源（発電所）から複数の需要先（工場）へ電力を送る問題は、最大流問題（Max Flow）に帰着して解くことができます。

具体的には、電力の湧き出し口となる「ソース（超頂点）」と、最終的な吸収先となる「シンク（超頂点）」を新たに用意します。 - ソースから各発電所へ、最大供給量 \(W_k\) の辺を張ります。 - 各工場からシンクへ、必要電力 \(B_i\) の辺を張ります。 - 送電線は、容量 \(C_j\) の無向辺（双方向に流せる辺）として張ります。

このグラフ上でソースからシンクへ最大流を流し、その流量が「全工場の必要電力の合計 \(\sum B_i\)」に達していれば、全員に十分な電力が供給できている（Yes）と判定できます。

しかし、この問題では発電所が順番に故障していきます。故障するたびにグラフから辺を削除して最大流をゼロから計算し直すと、非効率になる場合があります（特にフロー問題において「辺の削除」は扱いにくい操作です）。

そこで、時間を逆から考える（逆順に処理する）という競技プログラミングの定石を使います。 「発電所が順番に壊れていく」という過程を逆から見ると、「すべての故障が終わった最終状態からスタートし、発電所が順番に直っていく（辺が追加される）」と捉えることができます。辺の追加であれば、それまで流した電力（残余グラフ）を保持したまま、追加で流せる分だけを計算すればよいので、非常に効率的かつ簡単に実装できます。

アルゴリズム

1. 頂点として、各工場（\(1 \sim N\)）、各発電所（\(N+1 \sim N+K\)）に加えて、ソースとシンクの2つの超頂点を用意します。
2. 各工場からシンクへ、容量 \(B_i\) の有向辺を張ります。
3. 送電網の各辺について、双方向に容量 \(C_j\) を持つ無向辺を張ります。
4. すべてのイベントが終了した後の状態を構築します。最後まで壊れなかった発電所についてのみ、ソースからその発電所へ容量 \(W_k\) の有向辺を張ります。
5. この状態でソースからシンクへの最大流を計算し、流量が \(\sum B_i\) と等しければ最後のイベント後の答えは Yes、そうでなければ No と記録します。
6. イベントを最後（\(Q\) 番目）から最初（\(1\) 番目）に向かって逆順にたどります。
   • イベント \(t\) で故障した発電所 \(S_t\) を「復旧」させるため、ソースから発電所 \(S_t\) へ容量 \(W_{S_t}\) の有向辺を追加します。
   • 既存のグラフ上で追加で最大流を流し、合計流量が \(\sum B_i\) に達しているかを判定して記録します。
7. すべてのイベントを遡り終えたら、記録した判定結果を逆順（元の時間軸の順）にして出力します。

計算量

• 時間計算量: \(O(Q V^2 E)\)
  • 頂点数 \(V = N + K + 2\)、辺数 \(E \approx N + K + 2M\) です。
  • Dinic法による最大流計算の最悪計算量は \(O(V^2 E)\) です。これを初期状態と \(Q\) 回の辺追加ごとに行うため、理論上の最悪計算量は \(O(Q V^2 E)\) となります。
  • 今回の制約（\(V \le 66, E \le 666, Q \le 32\)）では最大でも \(10^8\) 程度の計算回数に見えますが、Dinic法は実際には最悪計算量よりはるかに高速に動作し、さらに辺を追加して差分だけを流すため、実行時間は一瞬（数ミリ秒）で終わります。
• 空間計算量: \(O(V + E)\)
  • グラフの頂点と辺（および残余グラフの管理）を保持するためのメモリ空間です。

実装のポイント

• 無向辺の表現: Dinic法で無向辺を追加する際は、互いに逆向きの容量 \(C_j\) の有向辺を2本張ることで表現します（正解コードの add_undirected_edge メソッド）。

• 「\(B_i\) 以上」の扱い: 問題文には「工場は \(B_i\) 以上の電力を受け取ることも可能」とありますが、シンクへの辺の容量をちょうど \(B_i\) に制限して問題ありません。なぜなら、\(B_i\) より多く流せる余裕がある場合でも、ちょうど \(B_i\) だけ流す（発電所からの供給を抑える）ようなフローが必ず存在するからです。

• 再帰上限の引き上げ: PythonでDinic法のような深い再帰を伴うDFSを実装する場合、sys.setrecursionlimit で再帰の上限を引き上げておく必要があります。

  ソースコード

import sys
import collections

class Dinic:
    def __init__(self, v, inf=10**18):
        self.v = v
        self.inf = inf
        self.graph = [[] for _ in range(v)]
        self.level = []
        self.iter = []

    def add_edge(self, fr, to, cap):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        self.graph[to].append([fr, 0, len(self.graph[fr]) - 1])
        
    def add_undirected_edge(self, fr, to, cap):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        self.graph[to].append([fr, cap, len(self.graph[fr]) - 1])

    def bfs(self, s):
        self.level = [-1] * self.v
        self.level[s] = 0
        queue = collections.deque([s])
        while queue:
            v = queue.popleft()
            level_v = self.level[v]
            for to, cap, rev in self.graph[v]:
                if cap > 0 and self.level[to] < 0:
                    self.level[to] = level_v + 1
                    queue.append(to)

    def dfs(self, v, t, f):
        if v == t:
            return f
        graph_v = self.graph[v]
        level_v = self.level[v]
        for i in range(self.iter[v], len(graph_v)):
            self.iter[v] = i
            edge = graph_v[i]
            to, cap, rev = edge
            if cap > 0 and level_v < self.level[to]:
                d = self.dfs(to, t, min(f, cap))
                if d > 0:
                    edge[1] -= d
                    self.graph[to][rev][1] += d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0] * self.v
            while True:
                f = self.dfs(s, t, self.inf)
                if f == 0:
                    break
                flow += f

def solve():
    sys.setrecursionlimit(2000)
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    
    idx = 3
    B = [int(x) for x in input_data[idx:idx+N]]
    idx += N
    
    W = [int(x) for x in input_data[idx:idx+K]]
    idx += K
    
    edges = []
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        c = int(input_data[idx+2])
        edges.append((u, v, c))
        idx += 3
        
    Q = int(input_data[idx])
    idx += 1
    S_events = [int(x) for x in input_data[idx:idx+Q]]
    
    V = N + K + 2
    SOURCE = 0
    SINK = N + K + 1
    
    dinic = Dinic(V)
    
    sum_B = sum(B)
    
    for i in range(N):
        dinic.add_edge(i + 1, SINK, B[i])
        
    for u, v, c in edges:
        dinic.add_undirected_edge(u, v, c)
        
    broken_set = set(S_events)
    
    for k in range(1, K + 1):
        if k not in broken_set:
            dinic.add_edge(SOURCE, N + k, W[k-1])
            
    current_flow = dinic.max_flow(SOURCE, SINK)
    
    ans = []
    
    for t in range(Q - 1, -1, -1):
        if current_flow >= sum_B:
            ans.append("Yes")
        else:
            ans.append("No")
            
        if t > 0:
            k = S_events[t]
            dinic.add_edge(SOURCE, N + k, W[k-1])
            current_flow += dinic.max_flow(SOURCE, SINK)
            
    ans.reverse()
    print('\n'.join(ans))

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。