Overview

In a network where \(N\) factories and \(K\) power plants are connected by power lines, power plants fail one by one, and we need to determine after each failure whether the electricity demand of all factories can still be met. This can be reduced to a maximum flow problem.

Analysis

Identifying the Essence of the Problem

Each factory \(i\) needs to receive at least \(B_i\) units of electricity, each power plant \(k\) can supply between \(0\) and \(W_k\) units of electricity, and power lines have capacity constraints. This is a classic network flow structure.

Conversion to a Maximum Flow Problem

To determine “Can the required electricity be delivered to all factories?”, we construct a flow network as follows:

1. Add a super source \(S\) and for each available power plant \(k\), add an edge \(S \to\) power plant \(k\) with capacity \(W_k\) (the upper limit of electricity the power plant can supply)
2. Add a super sink \(T\) and for each factory \(i\), add an edge factory \(i \to T\) with capacity \(B_i\) (the amount of electricity the factory requires)
3. Each power line \((U_j, V_j, C_j)\) is added as a bidirectional edge with capacity \(C_j\)

We compute the maximum flow from \(S\) to \(T\) on this network. If it is at least \(\sum_{i=1}^{N} B_i\) (the total demand of all factories), then all factories can be satisfied.

Why This Model is Correct

• Flow entering \(T\) can only arrive through factories
• Since the capacity of the edge factory \(i \to T\) is \(B_i\), at most \(B_i\) can be sent from factory \(i\) to \(T\)
• Maximum flow \(= \sum B_i\) means that all factory \(\to T\) edges are saturated, which means at least \(B_i\) has flowed into each factory
• Surplus electricity is not a problem because power plants can simply choose not to generate it

Processing Each Event

Each time a power plant fails in an event, we rebuild the network excluding the failed power plant and recompute the maximum flow. Since \(Q \leq K \leq 32\), \(N+K \leq 64\), and \(M \leq 300\), these are small enough that recomputing the flow each time is well within the time limit.

Algorithm

Apply Dinic’s algorithm (maximum flow) for each query.

1. Maintain the set of failed power plants disabled
2. After each event, execute the following:
   • Build a flow graph with \(N + K + 2\) nodes (internal nodes + super source + super sink)
   • Add edges from \(S\) only for available (non-failed) power plants
   • Add power lines as bidirectional edges (capacity \(C_j\) in each direction)
   • Compute the maximum flow using Dinic’s algorithm
   • If maximum flow \(\geq \sum B_i\), output Yes; otherwise output No

Implementation of bidirectional edges: For a normal directed edge, we add capacity \(C\) in the forward direction and capacity \(0\) in the reverse direction. However, for an undirected (bidirectional) edge, we add capacity \(C\) in both the forward and reverse directions.

Complexity

• Number of nodes \(V = N + K + 2 \leq 66\)

• Number of edges \(E = M + N + K \leq 364\)

• Complexity of Dinic’s algorithm: \(O(V^2 \cdot E)\)

• Number of queries: \(Q \leq 32\)

• Time complexity: \(O(Q \cdot V^2 \cdot E) = O(32 \times 66^2 \times 364) \approx 5 \times 10^7\)

• Space complexity: \(O(V + E)\)

Implementation Notes

• Adding bidirectional edges: In add_undirected_edge(u, v, cap), set capacity \(cap\) for \(u \to v\) and also capacity \(cap\) for \(v \to u\). Note that this differs from the usual reverse edge (with residual capacity \(0\)).

• Rebuilding the graph each time: Since flowing through the graph changes residual capacities, we reconstruct a new graph for each query.

• Judgment condition: Check whether the maximum flow \(= \sum B_i\). We verify that all factories’ demands are met by checking whether all edges with capacity \(B_i\) are saturated.

  Source Code

import sys
from collections import defaultdict, deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    def rd():
        nonlocal idx
        val = int(input_data[idx]); idx += 1; return val

    N = rd(); K = rd(); M = rd()
    B = [rd() for _ in range(N)]
    W = [rd() for _ in range(K)]
    edges_input = []
    for _ in range(M):
        u = rd(); v = rd(); c = rd()
        edges_input.append((u, v, c))
    Q = rd()
    events = [rd() for _ in range(Q)]

    # We need to solve a max-flow problem for each query.
    # Network:
    #   - Super source S, super sink T
    #   - For each factory i (node i, 1-indexed): edge from factory node to T with capacity B_i (demand)
    #     Actually, we need net(v) >= B_i for factories, meaning at least B_i flows into factory.
    #   - For each active power plant k (node N+k): edge from S to power plant node with capacity W_k
    #   - For each transmission line: bidirectional edge with capacity C_j
    #
    # The condition is: max flow from S to T >= sum(B_i)
    #
    # Model:
    #   Nodes: S=0, T=1, and nodes 2..N+K+1 representing points 1..N+K
    #   - For each active power plant k: S -> node(N+k) with capacity W_k
    #   - For each factory i: node(i) -> T with capacity B_i
    #   - For each transmission line (u,v,c): node(u) <-> node(v) with capacity c each direction
    #   - Factories can receive excess, so the edge to T is capacity B_i? No, factories need AT LEAST B_i.
    #     Excess is okay. So we can model: factory node -> T with capacity infinity? No.
    #     We want to check if we can send sum(B_i) to T. Each factory must contribute at least B_i to T.
    #     So edge from factory i to T with capacity = infinity, and we add a lower bound of B_i.
    #
    # Actually simpler: We just need each factory to receive >= B_i. 
    # Use: S -> power plants (cap W_k), transmission lines (cap C_j bidirectional), factories -> T (cap INF).
    # Then check if max_flow >= sum(B_i).
    # But this doesn't enforce that each factory gets at least B_i individually.
    #
    # Correct approach: use lower bounds on edges from factories to T.
    # Edge from factory i to T: lower bound B_i, upper bound INF.
    # Convert to standard max-flow using the standard lower-bound technique:
    #   - Subtract B_i from capacity, add B_i to supply of factory i and demand of T.
    # Alternatively, just set capacity of factory->T edge to a huge number and check max_flow >= sum(B_i).
    # Wait - that works only if there's no way to route flow to T except through factories. 
    # Since T is only connected to factories, yes, flow to T must come through factories.
    # But we need EACH factory to send at least B_i. A single factory could send more while another sends less.
    # So we need lower bounds. 
    #
    # Simpler: make edge from factory i -> T with capacity exactly B_i (not infinity).
    # Then max_flow >= sum(B_i) iff all factories are satisfied. Since capacity is B_i, 
    # max flow = sum(B_i) iff each edge is fully saturated = each factory gets exactly B_i.
    # Excess power just stays (but excess can flow into factory and... go nowhere? That violates conservation.)
    # We need a way to absorb excess. Add edges from each non-T, non-S node to a "waste" or just 
    # let excess stay at power plants (they don't have to generate).
    # Actually with the model: S->plants, plants/factories connected by transmission lines, factories->T (cap B_i),
    # flow conservation holds at all internal nodes. Power plants generate exactly what they send out.
    # Factories receive exactly what flows in, and send min(received, B_i) to T. Excess... can't go anywhere.
    # So we need a waste node or self-loops. 
    # Just add an edge from each factory to a waste node (or back to S) with infinite capacity? No.
    # Simplest: factories -> T with cap B_i. Add a "waste" node W connected from every node with INF cap, 
    # and S->W or W is just a sink. Actually just: every internal node -> T2 (waste sink) with INF, 
    # and we only care about flow reaching T (the real sink). This complicates things.
    #
    # Easiest correct model: capacity of factory->T = B_i. If max_flow == sum(B_i), answer is Yes.
    # Excess power simply isn't generated (power plants can generate 0 to W_k).

    total_demand = sum(B)

    def solve(disabled_set):
        # Dinic's max flow
        # node 0 = super source, node 1 = super sink
        # node i+2 for point i (1-indexed), so point i -> index i+1
        n_nodes = N + K + 2
        S = 0; T = 1

        # Adjacency list for Dinic's
        graph = [[] for _ in range(n_nodes)]

        def add_edge(u, v, cap):
            graph[u].append([v, cap, len(graph[v])])
            graph[v].append([u, 0, len(graph[u]) - 1])

        def add_undirected_edge(u, v, cap):
            graph[u].append([v, cap, len(graph[v])])
            graph[v].append([u, cap, len(graph[u]) - 1])

        # Power plants
        for k in range(1, K + 1):
            if k not in disabled_set:
                add_edge(S, (N + k) + 1, W[k - 1])

        # Factories
        for i in range(1, N + 1):
            add_edge(i + 1, T, B[i - 1])

        # Transmission lines
        for (u, v, c) in edges_input:
            add_undirected_edge(u + 1, v + 1, c)

        # Dinic's BFS
        level = [0] * n_nodes
        it = [0] * n_nodes

        def bfs():
            for i in range(n_nodes):
                level[i] = -1
            level[S] = 0
            q = deque()
            q.append(S)
            while q:
                v = q.popleft()
                for e in graph[v]:
                    if e[1] > 0 and level[e[0]] < 0:
                        level[e[0]] = level[v] + 1
                        q.append(e[0])
            return level[T] >= 0

        def dfs(v, t, f):
            if v == t:
                return f
            while it[v] < len(graph[v]):
                e = graph[v][it[v]]
                if e[1] > 0 and level[v] < level[e[0]]:
                    d = dfs(e[0], t, min(f, e[1]))
                    if d > 0:
                        e[1] -= d
                        graph[e[0]][e[2]][1] += d
                        return d
                it[v] += 1
            return 0

        flow = 0
        while bfs():
            for i in range(n_nodes):
                it[i] = 0
            while True:
                f = dfs(S, T, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow >= total_demand

    disabled = set()
    results = []
    for t in range(Q):
        disabled.add(events[t])
        if solve(disabled):
            results.append("Yes")
        else:
            results.append("No")

    sys.stdout.write("\n".join(results) + "\n")

main()

---

This editorial was generated by claude4.6opus-thinking.