Overview

In a network where multiple power plants and factories are connected by power lines, power plants fail one by one in sequence. The problem asks us to determine at each stage whether sufficient electricity can still be supplied to all factories.

Approach

The problem of sending electricity from multiple sources (power plants) to multiple destinations (factories) can be reduced to a maximum flow problem (Max Flow).

Specifically, we introduce a new “source (super vertex)” as the origin of electricity and a “sink (super vertex)” as the final destination. - From the source to each power plant, add an edge with maximum supply capacity \(W_k\). - From each factory to the sink, add an edge with required power \(B_i\). - Power lines are added as undirected edges (edges that allow flow in both directions) with capacity \(C_j\).

On this graph, we compute the maximum flow from source to sink. If the flow equals the “total required power of all factories \(\sum B_i\)”, then sufficient power is being supplied to everyone (Yes).

However, in this problem, power plants fail one by one. If we delete edges from the graph and recompute the maximum flow from scratch each time a failure occurs, it can be inefficient (edge deletion is particularly difficult to handle in flow problems).

Therefore, we use a standard competitive programming technique: process events in reverse chronological order. Viewing the process of “power plants failing one by one” in reverse, we can interpret it as “starting from the final state where all failures have occurred, and power plants are restored one by one (edges are added)”. With edge addition, we can keep the existing flow (residual graph) intact and only compute the additional flow that can be pushed, making the implementation both very efficient and straightforward.

Algorithm

1. Prepare vertices for each factory (\(1 \sim N\)), each power plant (\(N+1 \sim N+K\)), plus two super vertices: source and sink.
2. Add a directed edge with capacity \(B_i\) from each factory to the sink.
3. For each power line in the grid, add an undirected edge with capacity \(C_j\) in both directions.
4. Construct the state after all events have completed. Only for power plants that never failed, add a directed edge with capacity \(W_k\) from the source to that power plant.
5. Compute the maximum flow from source to sink in this state. If the flow equals \(\sum B_i\), record the answer after the last event as Yes; otherwise record No.
6. Traverse events in reverse order, from the \(Q\)-th to the \(1\)-st.
   • To “restore” power plant \(S_t\) that failed in event \(t\), add a directed edge with capacity \(W_{S_t}\) from the source to power plant \(S_t\).
   • Compute the additional maximum flow on the existing graph and check whether the total flow has reached \(\sum B_i\), recording the result.
7. After processing all events in reverse, output the recorded results in reverse order (i.e., in the original chronological order).

Complexity

• Time complexity: \(O(Q V^2 E)\)
  • The number of vertices is \(V = N + K + 2\), and the number of edges is \(E \approx N + K + 2M\).
  • The worst-case complexity of maximum flow computation using Dinic’s algorithm is \(O(V^2 E)\). Since this is performed for the initial state and after each of \(Q\) edge additions, the theoretical worst-case complexity is \(O(Q V^2 E)\).
  • With the given constraints (\(V \le 66, E \le 666, Q \le 32\)), this appears to be at most around \(10^8\) operations. However, Dinic’s algorithm runs far faster than its worst-case bound in practice, and since we only push the incremental flow after adding edges, the execution time finishes in an instant (a few milliseconds).
• Space complexity: \(O(V + E)\)
  • Memory space for storing the graph’s vertices, edges, and residual graph management.

Implementation Notes

• Representing undirected edges: When adding an undirected edge in Dinic’s algorithm, represent it by adding two directed edges with capacity \(C_j\) in opposite directions (see the add_undirected_edge method in the solution code).

• Handling “\(B_i\) or more”: The problem states that “a factory can receive \(B_i\) or more power,” but it is perfectly fine to limit the capacity of the edge to the sink to exactly \(B_i\). This is because even if there is room to flow more than \(B_i\), a flow that sends exactly \(B_i\) (by reducing supply from power plants) always exists.

• Raising the recursion limit: When implementing DFS with deep recursion, such as in Dinic’s algorithm in Python, you need to raise the recursion limit using sys.setrecursionlimit.

  Source Code

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

This editorial was generated by gemini-3.1-pro-thinking.