Overview

This problem involves determining whether all factories can receive their required power when power plants fail sequentially, on a graph representing power flow in a transmission network. This can be modeled as a classic maximum flow problem.

Analysis

In this problem, if we consider the power required by factories as “demand,” the power that power plants can supply as “supply capacity,” and transmission lines as edges with capacities, we can treat the entire system as a network flow problem.

Key Observations

• Factories must receive at least a minimum amount of power → lower bound on inflow
• Power plants have an upper limit on supply → upper bound on outflow
• Conservation of power (inflow = outflow) holds at each node

To handle such conditions, it is effective to reduce the problem to a maximum flow problem.

Issues with a Naive Approach

While it is possible to solve this by simply rebuilding the graph and checking if flow is feasible for each event, recomputing the maximum flow every time would be too slow. However, in this case, using a maximum flow algorithm is sufficiently fast.

Solution

For each event, set the failing power plant to inactive, compute the maximum flow using the remaining power plants, and output Yes if it is at least the total demand of all factories, or No otherwise.

Algorithm

This problem can be efficiently solved using the Dinic’s algorithm for maximum flow.

Modeling Procedure

1. Set up graph nodes as follows:

   • Nodes \(0\) to \(N-1\): Factories
   • Nodes \(N\) to \(N+K-1\): Power plants
   • Node \(N+K\): Super source (aggregation of supply sources)
   • Node \(N+K+1\): Super sink (aggregation of demand destinations)

2. Edge construction:

   • Super source → each active power plant: capacity \(W_k\)
   • Each factory → super sink: capacity \(B_i\)
   • Transmission lines (undirected) → bidirectional edges with capacity \(C_j\)

3. For each event, deactivate the failed power plant and recompute the maximum flow.

4. If the maximum flow is at least the total demand (\(\sum B_i\)), output Yes; otherwise, output No.

Complexity

• The time complexity of Dinic’s algorithm is generally \(O(V^2 E)\) (\(V\): number of vertices, \(E\): number of edges).

• In this problem, the number of vertices is at most \(N + K + 2 \leq 66\), and the number of edges is at most a few hundred, so it runs sufficiently fast.

• Since the maximum flow is recomputed for each query, the overall complexity is:

• Time complexity: \(O(Q \cdot V^2 E)\)

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

Implementation Notes

• Node indices are unified as 0-indexed (in particular, subtract 1 from transmission line inputs)

• Each transmission line is bidirectional, so two directed edges are added

• A new Dinic instance is created for each event, computing the flow on the latest graph structure

• Check whether max_flow is at least the total demand

  Source Code

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.level = [0] * n
        self.ptr = [0] * n

    def add_edge(self, u, v, cap):
        # forward edge
        forward = [v, cap, len(self.graph[v])]
        # backward edge
        backward = [u, 0, len(self.graph[u])]
        self.graph[u].append(forward)
        self.graph[v].append(backward)

    def bfs(self, source, sink):
        self.level = [-1] * self.n
        self.level[source] = 0
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v, cap, rev_index in self.graph[u]:
                if self.level[v] == -1 and cap > 0:
                    self.level[v] = self.level[u] + 1
                    queue.append(v)
        return self.level[sink] != -1

    def dfs(self, u, sink, flow):
        if u == sink:
            return flow
        while self.ptr[u] < len(self.graph[u]):
            v, cap, rev_index = self.graph[u][self.ptr[u]]
            if self.level[v] == self.level[u] + 1 and cap > 0:
                bottleneck = self.dfs(v, sink, min(flow, cap))
                if bottleneck > 0:
                    self.graph[u][self.ptr[u]][1] -= bottleneck
                    self.graph[v][rev_index][1] += bottleneck
                    return bottleneck
            self.ptr[u] += 1
        return 0

    def max_flow(self, source, sink):
        flow = 0
        while self.bfs(source, sink):
            self.ptr = [0] * self.n
            while True:
                pushed = self.dfs(source, sink, float('inf'))
                if pushed == 0:
                    break
                flow += pushed
        return flow

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    B = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    W = [int(data[idx + i]) for i in range(K)]
    idx += K
    
    edges = []
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        c = int(data[idx]); idx += 1
        edges.append((u, v, c))
    
    Q = int(data[idx]); idx += 1
    S = [int(data[idx + i]) - 1 for i in range(Q)]
    idx += Q
    
    total_demand = sum(B)
    
    # Node indices:
    # 0 to N-1: factories
    # N to N+K-1: power plants
    # N+K: super source
    # N+K+1: super sink
    
    SOURCE = N + K
    SINK = N + K + 1
    TOTAL_NODES = N + K + 2
    
    # Initially all power plants are active
    active = [True] * K
    
    results = []
    
    for q in range(Q):
        # Disable the failing plant
        plant = S[q]
        active[plant] = False
        
        # Build the network
        dinic = Dinic(TOTAL_NODES)
        
        # Connect super source to each active power plant with capacity W[k]
        for k in range(K):
            if active[k]:
                dinic.add_edge(SOURCE, N + k, W[k])
        
        # Connect each factory to super sink with demand B[i]
        for i in range(N):
            dinic.add_edge(i, SINK, B[i])
        
        # Add transmission lines (bidirectional)
        for u, v, c in edges:
            dinic.add_edge(u, v, c)
            dinic.add_edge(v, u, c)
        
        # Compute maximum flow
        max_flow_value = dinic.max_flow(SOURCE, SINK)
        
        # Check if all demands are satisfied
        if max_flow_value >= total_demand:
            results.append("Yes")
        else:
            results.append("No")
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.