Overview

Each time a power plant fails and the “set of available power plants” changes, we need to determine whether it is possible to deliver at least the required amount \(B_i\) of electricity to every factory, subject to transmission capacity constraints. This can be reduced to determining, for each event, whether a “circulation with lower bounds” exists, which can be solved using maximum flow.

Analysis

Key Observation: This is a “Flow Feasibility Problem”

We need to determine whether there exists a flow satisfying flow conservation (inflow = outflow) at each node, along with:

• Factory: net inflow \(\ge B_i\)
• Power plant (active): net inflow \(\in [-W_k, 0]\) (can supply up to \(W_k\))
• Power plant (inactive): net inflow \(= 0\) (cannot supply, but can relay)

There is no objective function — we only need to determine “is it feasible or not.”

Why a Naive Approach is Difficult

• Factories require “at least \(B_i\)” while power plants have “at most \(W_k\),” so it doesn’t directly reduce to a simple \(s\)-\(t\) max-flow form (the inequalities are mixed).
• Furthermore, transmission lines are undirected with \(-C \le f \le C\) (negative means reverse direction), which appears cumbersome to handle.
• There are up to \(Q \le 32\) events, and we need to check feasibility each time.

Solution Strategy

We use standard techniques to handle inequalities and undirected edges:

• Undirected edge \(\leftrightarrow\) two directed edges (capacity \(C\) in both directions)
• Express “factory demand” and “power plant supply limit” as edges with lower bound constraints
• Existence of a circulation with lower bounds \(\rightarrow\) determined by a single max-flow computation

Since \(N, K \le 32\), we can rebuild the graph and run max-flow for each event, which is fast enough.

Algorithm

1. Graph Construction (Expressed as a Circulation)

Nodes are \(1 \ldots N+K\). We also add auxiliary nodes:

• \(SS\): acts as a “source” from which power plants receive electricity (in code: SS = 0)
• \(TT\): acts as a “sink” where factories consume electricity (in code: TT = N+K+1)

(a) Undirected Transmission Lines

A transmission line \((u, v)\) with capacity \(C\) is converted into two directed edges:

• \(u \to v\) (capacity \(C\))
• \(v \to u\) (capacity \(C\))

This may allow flow in both directions simultaneously, but the net difference corresponds to the original \(f\), and the achievable “net flow” stays within \([-C, C]\), so this is sufficient for feasibility checking.

(b) Power Plants (Supply up to \(W_k\) if Active)

For power plant \(k\) (node \(N+k\)):

• Add edge \(SS \to (N+k)\) with capacity \(W_k\) (capacity \(0\) if inactive)

If \(x\) units flow through this edge, flow conservation forces the power plant to push \(x\) units outward, effectively representing “supply up to \(W_k\).” When inactive, simply setting the capacity to \(0\) prohibits supply while still allowing relay.

© Factories (Must Receive at Least \(B_i\))

For factory \(i\):

• Add edge \(i \to TT\) with lower bound \(B_i\), upper bound \(\infty\)

Since at least \(B_i\) must flow through this edge, flow conservation requires factory \(i\) to receive at least \(B_i\) inflow, representing “receiving at least the required amount” (any surplus can flow through this edge as extra).

(d) \(TT \to SS\) (Infinite Capacity)

Finally, add:

• \(TT \to SS\) (lower bound \(0\), upper bound \(\infty\))

to close the “circulation.” This allows the electricity consumed by factories to return to \(SS\), fitting everything into the flow conservation framework.

---

2. Feasibility Check for Circulation with Lower Bounds (Reduction to Max-Flow)

This is the standard technique for handling an edge \(a \to b\) with lower bound \(L\) and upper bound \(U\):

• Set the edge capacity to \((U - L)\)
• Update the balance of each node accordingly:
  • balance[a] -= L
  • balance[b] += L

After processing all edges, a node with balance[v] > 0 means “it needs that much additional inflow,” and balance[v] < 0 means “it needs that much additional outflow.”

Then, create a new super-source \(S\) and super-sink \(T\):

• balance[v] > 0: add edge \(S \to v\) with capacity balance[v]
• balance[v] < 0: add edge \(v \to T\) with capacity -balance[v]

Run max-flow from \(S\) to \(T\). At this point:

• The total required flow from \(S\): need = Σ max(balance[v], 0)

If all of it can be pushed (max-flow = need), then the circulation exists; otherwise, it is infeasible.

The function feasible() in the code performs this check using Dinic’s algorithm.

---

3. Processing Each Event

When power plant \(s\) fails due to an event, set active[s] = False and:

• Set the capacity of \(SS \to (N+s)\) to \(0\) and run the feasibility check

This is done each time (in the code, the graph is rebuilt from scratch each time).

Complexity

The number of nodes is at most \(V \le (N+K) + 4 \le 68\), and the number of edges is at most \(E \le 2M + (N+K) + O(V) \le 700\).

• Time complexity: \(O\!\left(Q \cdot E V^2\right)\) (based on the general worst-case complexity of Dinic’s algorithm, but sufficiently fast under this problem’s constraints)
• Space complexity: \(O(E+V)\)

Implementation Notes

• The factory requirement “\(\ge B_i\)” is naturally handled by a lower-bounded edge \(i \to TT\) (lower bound \(B_i\)).

• The fact that inactive power plants can still relay is achieved by simply “setting the capacity of the supply edge \(SS \to \text{power plant}\) to \(0\)” (without removing the node itself).

• Undirected edges are converted to two directed edges with capacity \(C\) in both directions, which is fine (no issues for feasibility checking).

• Since the sum of capacities and lower bounds can reach the order of \(10^9\), use 64-bit integers safely with something like INF = 10^{18}.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.