公式
E - 送電ネットワークの停電危機 / Power Grid Blackout Crisis 解説 by admin
Claude 4.6 Opus (Thinking)概要
\(N\) 個の工場と \(K\) 個の発電所が送電線で結ばれたネットワークにおいて、発電所が順次故障していく中で、各故障後に全工場の電力需要を満たせるかを判定する問題です。これは最大フロー問題に帰着できます。
考察
問題の本質を見抜く
各工場 \(i\) は \(B_i\) 以上の電力を受け取る必要があり、各発電所 \(k\) は \(0\) 以上 \(W_k\) 以下の電力を供給でき、送電線には容量制約があります。これは典型的なネットワークフローの構造です。
最大フロー問題への変換
「すべての工場に必要な電力を届けられるか？」を判定するために、以下のようにフローネットワークを構築します：
- 超源点 \(S\) を追加し、使用可能な各発電所 \(k\) に対して \(S \to\) 発電所\(k\) に容量 \(W_k\) の辺を張る（発電所が供給できる電力の上限）
- 超流入点 \(T\) を追加し、各工場 \(i\) に対して 工場\(i \to T\) に容量 \(B_i\) の辺を張る（工場が必要とする電力量）
- 各送電線 \((U_j, V_j, C_j)\) は双方向に容量 \(C_j\) の辺として追加
このネットワーク上で \(S\) から \(T\) への最大フローを求め、それが \(\sum_{i=1}^{N} B_i\)（全工場の需要合計）以上であれば全工場を満たせます。
なぜこのモデルが正しいのか
- \(T\) に流入するフローは、工場を経由してしか到達できません
- 工場 \(i \to T\) の辺の容量が \(B_i\) なので、工場 \(i\) からは最大 \(B_i\) しか \(T\) に送れません
- 最大フロー \(= \sum B_i\) ということは、すべての工場 \(\to T\) の辺が満杯、つまり全工場に \(B_i\) 以上が流入していることを意味します
- 余剰電力は発電所がそもそも生成しなければよいので問題になりません
イベントごとの処理
各イベントで発電所が1つ故障するたびに、故障した発電所を除外してネットワークを再構築し、最大フローを計算します。\(Q \leq K \leq 32\) かつ \(N+K \leq 64\)、\(M \leq 300\) と小さいため、毎回フローを再計算しても十分間に合います。
アルゴリズム
Dinic法（最大フロー）を各クエリごとに適用します。
- 故障した発電所の集合
disabledを管理する - 各イベント後に以下を実行：
- ノード数 \(N + K + 2\)（内部ノード＋超源点＋超流入点）のフローグラフを構築
- 使用可能な発電所のみ \(S\) からの辺を追加
- 送電線は双方向辺（各方向に容量 \(C_j\)）として追加
- Dinic法で最大フローを計算
- 最大フロー \(\geq \sum B_i\) なら
Yes、そうでなければNo
双方向辺の実装: 通常の有向辺は順方向に容量 \(C\)、逆方向に容量 \(0\) ですが、無向辺（双方向）は順方向・逆方向ともに容量 \(C\) で追加します。
計算量
ノード数 \(V = N + K + 2 \leq 66\)
辺数 \(E = M + N + K \leq 364\)
Dinic法の計算量: \(O(V^2 \cdot E)\)
クエリ数: \(Q \leq 32\)
時間計算量: \(O(Q \cdot V^2 \cdot E) = O(32 \times 66^2 \times 364) \approx 5 \times 10^7\) 程度
空間計算量: \(O(V + E)\)
実装のポイント
双方向辺の追加:
add_undirected_edge(u, v, cap)では、\(u \to v\) に容量 \(cap\)、\(v \to u\) にも容量 \(cap\) を設定します。通常の逆辺（残余容量 \(0\)）とは異なるので注意が必要です。毎回グラフを再構築: フローを流すとグラフの残余容量が変わるため、各クエリで新しいグラフを作り直します。
判定条件: 最大フロー \(= \sum B_i\) かどうか。容量 \(B_i\) の辺がすべて飽和しているかで全工場の需要充足を確認します。
ソースコード
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()
この解説は claude4.6opus-thinking によって生成されました。
投稿日時:
最終更新: