概要

発電所の故障で「使える発電所の集合」が変わるたびに、送電容量制約の下で全工場に必要量 \(B_i\) 以上の電力を届けられるかを判定します。
これは各イベントごとに「下限制約付き循環（circulation with lower bounds）が存在するか」を最大流で判定する問題に帰着できます。

考察

重要な観察：これは“フローの存在判定”

各地点でフロー保存（入ってくる量＝出ていく量）を満たしつつ、

• 工場：正味流入 \(\ge B_i\)
• 発電所（稼働）：正味流入 \(\in [-W_k, 0]\)（最大 \(W_k\) まで供給できる）
• 発電所（停止）：正味流入 \(=0\)（供給は不可だが中継は可能）

を満たすフローが存在するかを問われています。目的関数はなく「可能かどうか」だけです。

素朴にやると難しい理由

• 工場は「少なくとも \(B_i\)」であり、発電所は「最大 \(W_k\)」なので、単純な \(s\)-\(t\) 最大流の形にそのまま落としにくいです（不等式が混ざる）。
• さらに送電線は無向で \(-C \le f \le C\) という形（負なら逆向き）なので扱いが面倒に見えます。
• イベントは最大 \(Q \le 32\) 回あり、毎回判定が必要です。

解決方針

不等式や無向辺をまとめて扱える典型手法として、

• 無向辺 \(\leftrightarrow\) 有向辺2本（両方向に容量 \(C\)）
• 「工場の必要量」「発電所の供給上限」を、下限制約付きの辺として表現
• 下限制約付き循環の存在判定 \(\rightarrow\) 1回の最大流で判定

にします。\(N,K \le 32\) なので、各イベントごとにグラフを作り直して最大流を流しても十分間に合います。

アルゴリズム

1. グラフの作り方（循環として表現）

地点は \(1 \ldots N+K\)。さらに補助頂点を追加します：

• \(SS\)：発電所から電力を“受け取る元”のような役（コードでは SS = 0）
• \(TT\)：工場が電力を“消費して集まる先”（コードでは TT = N+K+1）

(a) 無向送電線

送電線 \((u,v)\)、容量 \(C\) は、次の2本の有向辺にします：

• \(u \to v\)（容量 \(C\)）
• \(v \to u\)（容量 \(C\)）

こうすると、両方向に流してしまう可能性はありますが、最終的な差分が元の \(f\) に対応し、到達可能な「正味の流れ」は \([-C, C]\) に収まるため、存在判定としてはこれで十分です。

(b) 発電所（稼働していれば最大 \(W_k\) 供給）

発電所 \(k\)（頂点 \(N+k\)）について、

• \(SS \to (N+k)\) に容量 \(W_k\)（停止なら容量 \(0\)）

を張ります。ここを \(x\) 流すと、発電所は保存則によりその \(x\) を外へ押し出す必要があり、結果として「最大 \(W_k\) まで供給」を表現できます。停止時は容量 \(0\) にするだけで、供給だけ禁止し、中継は引き続き可能です。

© 工場（少なくとも \(B_i\) 受け取りたい）

工場 \(i\) について、

• \(i \to TT\) に 下限 \(B_i\)、上限 \(\infty\)

を張ります。この辺に最低でも \(B_i\) 流さないといけないため、工場 \(i\) は保存則から最低 \(B_i\) の流入を得る必要があり、「必要量以上の受電」を表せます（余剰はこの辺に多めに流せばよい）。

(d) \(TT \to SS\)（無限大）

最後に

• \(TT \to SS\)（下限 \(0\)、上限 \(\infty\)）

を張って“循環”にします。これにより、工場で消費された分が \(SS\) に戻り、全体をフロー保存の枠組みに乗せられます。

---

2. 下限制約付き循環の判定（最大流への変換）

下限 \(L\)・上限 \(U\) の辺 \(a \to b\) を扱う定石です：

• 容量を \((U-L)\) にして辺を張る
• その代わりに各頂点の収支 balance を更新：
  • balance[a] -= L
  • balance[b] += L

全辺処理後、balance[v] > 0 の頂点には「その分だけ流入が必要」、balance[v] < 0 の頂点には「その分だけ流出が必要」という意味になります。

そこで新たに超始点 \(S\)・超終点 \(T\) を作り、

• balance[v] > 0：\(S \to v\) に容量 balance[v]
• balance[v] < 0：\(v \to T\) に容量 -balance[v]

を張り、\(S\) から \(T\) に最大流を流します。
このとき

• \(S\) から出る必要総量 need = Σ max(balance[v],0)

が すべて流し切れた（最大流 = need）なら循環が存在、そうでなければ不可能です。

本コードの feasible() はこの判定を Dinic 法で行っています。

---

3. 各イベント処理

イベントで発電所 \(s\) が故障したら active[s]=False とし、

• \(SS \to (N+s)\) の容量を \(0\) として判定

を毎回やります（コードでは毎回グラフを作り直しています）。

計算量

頂点数は高々 \(V \le (N+K) + 4 \le 68\) 程度、辺数も \(E \le 2M + (N+K) + O(V) \le 700\) 程度です。

• 時間計算量: \(O\!\left(Q \cdot E V^2\right)\)（Dinic 法の一般最悪計算量ベース、ただし本問題の制約では十分高速）
• 空間計算量: \(O(E+V)\)

実装のポイント

• 工場の「\(\ge B_i\)」は下限付き辺 \(i \to TT\)（下限 \(B_i\)）で表現すると自然に扱えます。

• 発電所停止後も中継可能である点は、「供給辺 \(SS \to 発電所\) の容量を \(0\) にする」だけで再現できます（頂点自体を消さない）。

• 無向辺は 両方向に容量 \(C\) の有向辺2本にしてOK（存在判定では問題になりません）。

• 容量や下限の総和が \(10^9\) オーダーで大きくなるので、INF = 10^18 のように 64bit整数で安全に扱います。

  ソースコード

import sys
from collections import deque

INF = 10**18

class Edge:
    __slots__ = ("to", "rev", "cap")
    def __init__(self, to, rev, cap):
        self.to = to
        self.rev = rev
        self.cap = cap

class Dinic:
    __slots__ = ("n", "g", "level")
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]
        self.level = [-1] * n

    def add_edge(self, fr, to, cap):
        fwd = Edge(to, len(self.g[to]), cap)
        rev = Edge(fr, len(self.g[fr]), 0)
        self.g[fr].append(fwd)
        self.g[to].append(rev)

    def bfs(self, s, t):
        level = self.level
        for i in range(self.n):
            level[i] = -1
        q = deque([s])
        level[s] = 0
        while q:
            v = q.popleft()
            nv = level[v] + 1
            for e in self.g[v]:
                if e.cap > 0 and level[e.to] < 0:
                    level[e.to] = nv
                    if e.to == t:
                        return True
                    q.append(e.to)
        return level[t] >= 0

    def dfs(self, v, t, f, it):
        if v == t:
            return f
        gv = self.g[v]
        i = it[v]
        while i < len(gv):
            e = gv[i]
            if e.cap > 0 and self.level[e.to] == self.level[v] + 1:
                d = self.dfs(e.to, t, f if f < e.cap else e.cap, it)
                if d:
                    e.cap -= d
                    self.g[e.to][e.rev].cap += d
                    return d
            i += 1
            it[v] = i
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            it = [0] * self.n
            while True:
                f = self.dfs(s, t, INF, it)
                if not f:
                    break
                flow += f
        return flow

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = 0
    N = data[it]; K = data[it+1]; M = data[it+2]; it += 3
    B = data[it:it+N]; it += N
    W = data[it:it+K]; it += K

    base_edges = []
    for _ in range(M):
        u = data[it]; v = data[it+1]; c = data[it+2]; it += 3
        base_edges.append((u, v, c))
        base_edges.append((v, u, c))

    Q = data[it]; it += 1
    S_list = data[it:it+Q]

    SS = 0
    TT = N + K + 1
    base_node_count = N + K + 2  # 0..TT

    active = [True] * K

    def feasible():
        S = base_node_count
        T = base_node_count + 1
        din = Dinic(base_node_count + 2)
        balance = [0] * base_node_count

        def add_lb_edge(a, b, low, up):
            din.add_edge(a, b, up - low)
            balance[a] -= low
            balance[b] += low

        for u, v, c in base_edges:
            add_lb_edge(u, v, 0, c)

        for k in range(1, K + 1):
            cap = W[k - 1] if active[k - 1] else 0
            add_lb_edge(SS, N + k, 0, cap)

        for i in range(1, N + 1):
            add_lb_edge(i, TT, B[i - 1], INF)

        add_lb_edge(TT, SS, 0, INF)

        need = 0
        for v in range(base_node_count):
            b = balance[v]
            if b > 0:
                din.add_edge(S, v, b)
                need += b
            elif b < 0:
                din.add_edge(v, T, -b)

        return din.max_flow(S, T) == need

    out = []
    for s in S_list:
        active[s - 1] = False
        out.append("Yes" if feasible() else "No")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。