题解：AtCoder AT_awc0031_e Power Grid Blackout Crisis

【题目来源】

AtCoder：E - Power Grid Blackout Crisis

【题目描述】

Takahashi manages the power supply system of a certain region. This region has \(N\) factories and \(K\) power plants, which are connected by transmission lines forming a power transmission network.
高桥负责管理某地区的电力供应系统。该地区有 \(N\) 个工厂和 \(K\) 个发电厂，它们通过输电线路连接形成一个输电网络。

The locations are numbered from \(1\) to \(N + K\), where locations \(1\) through \(N\) correspond to factories, and locations \(N + 1\) through \(N + K\) correspond to power plants. Specifically, factory \(i\) (\(1 \leq i \leq N\)) is located at location \(i\), and power plant \(k\) (\(1 \leq k \leq K\)) is located at location \(N + k\).
地点编号从 \(1\) 到 \(N + K\)，其中地点 \(1\) 到 \(N\) 对应工厂，地点 \(N + 1\) 到 \(N + K\) 对应发电厂。具体来说，工厂 \(i\)（\(1 \leq i \leq N\)）位于地点 \(i\)，发电厂 \(k\)（\(1 \leq k \leq K\)）位于地点 \(N + k\)。

The transmission network consists of \(N + K\) locations connected by \(M\) transmission lines. Each transmission line \(j\) (\(1 \leq j \leq M\)) bidirectionally connects location \(U_j\) and location \(V_j\), and can transmit up to \(C_j\) megawatts of power per day. Specifically, letting \(f_j\) megawatts denote the amount of power flowing through transmission line \(j\) in the direction from location \(U_j\) to location \(V_j\), the constraint \(-C_j \leq f_j \leq C_j\) must be satisfied. Here, \(f_j > 0\) means power is transmitted from location \(U_j\) to location \(V_j\), and \(f_j < 0\) means power is transmitted from location \(V_j\) to location \(U_j\).
输电网络由 \(M\) 条输电线路连接 \(N + K\) 个地点构成。每条输电线路 \(j\)（\(1 \leq j \leq M\)）双向连接地点 \(U_j\) 和地点 \(V_j\)，每天最多可传输 \(C_j\) 兆瓦的电力。具体来说，设 \(f_j\) 兆瓦为通过输电线路 \(j\) 从地点 \(U_j\) 流向地点 \(V_j\) 方向的功率，必须满足约束 \(-C_j \leq f_j \leq C_j\)。这里，\(f_j > 0\) 表示电力从地点 \(U_j\) 传输到地点 \(V_j\)，\(f_j < 0\) 表示电力从地点 \(V_j\) 传输到地点 \(U_j\)。

Each power plant \(k\) (\(1 \leq k \leq K\)), while operational, can supply any amount of power between \(0\) and \(W_k\) megawatts per day. Each factory \(i\) (\(1 \leq i \leq N\)) needs to receive at least \(B_i\) megawatts of power per day to operate. A factory may receive more than \(B_i\) megawatts of power; it operates without issues even if surplus power flows in.
每个发电厂 \(k\)（\(1 \leq k \leq K\)）在运行时，每天可供应 \(0\) 到 \(W_k\) 兆瓦之间的任意电量。每个工厂 \(i\)（\(1 \leq i \leq N\)）每天需要接收至少 \(B_i\) 兆瓦的电力才能运营。工厂可以接收超过 \(B_i\) 兆瓦的电力；即使有盈余电力流入，工厂也能正常运行。

At each location, flow conservation must hold for the power balance. The net inflow \(\mathrm{net}(v)\) at location \(v\) is defined as follows:
在每个地点，电力平衡必须满足流量守恒。地点 \(v\) 的净流入 \(\mathrm{net}(v)\) 定义如下：

\(\mathrm{net}(v) = \sum_{\substack{j :\, V_j = v}} f_j - \sum_{\substack{j :\, U_j = v}} f_j\)

To clarify the meaning of this formula: for transmission line \(j\), when \(f_j > 0\), power flows from \(U_j\) to \(V_j\), so \(f_j\) flows into location \(V_j\) and \(f_j\) flows out of location \(U_j\). When \(f_j < 0\), the reverse holds. \(\mathrm{net}(v)\) equals the total inflow to location \(v\) minus the total outflow from location \(v\), summed over all transmission lines connected to location \(v\).
为澄清此公式的含义：对于输电线路 \(j\)，当 \(f_j > 0\) 时，电力从 \(U_j\) 流向 \(V_j\)，因此 \(f_j\) 流入地点 \(V_j\) 且 \(f_j\) 流出地点 \(U_j\)。当 \(f_j < 0\) 时，情况相反。\(\mathrm{net}(v)\) 等于流入地点 \(v\) 的总流量减去流出地点 \(v\) 的总流量，对连接到地点 \(v\) 的所有输电线路求和。

The following conditions must be satisfied at each location:
每个地点必须满足以下条件：

• If location \(v\) is factory \(i\): \(\mathrm{net}(v) \geq B_i\). That is, a net inflow of at least \(B_i\) megawatts must flow into factory \(i\) through the transmission lines.
  如果地点 \(v\) 是工厂 \(i\)：\(\mathrm{net}(v) \geq B_i\)。也就是说，通过输电线路流入工厂 \(i\) 的净流入必须至少为 \(B_i\) 兆瓦。
• If location \(v\) is an operational power plant \(k\): \(-W_k \leq \mathrm{net}(v) \leq 0\). That is, power plant \(k\) can supply between \(0\) and \(W_k\) megawatts of power. Since the supplied power leaves the location, the net inflow is non-positive.
  如果地点 \(v\) 是运行中的发电厂 \(k\)：\(-W_k \leq \mathrm{net}(v) \leq 0\)。也就是说，发电厂 \(k\) 可供应 \(0\) 到 \(W_k\) 兆瓦的电力。由于供应的电力会离开该地点，净流入为非正。
• If location \(v\) is a non-operational power plant: \(\mathrm{net}(v) = 0\). It cannot supply power, but as long as inflow equals outflow, it can still function as a relay point through which power passes via transmission lines.
  如果地点 \(v\) 是非运行的发电厂：\(\mathrm{net}(v) = 0\)。它不能供应电力，但只要流入等于流出，它仍可作为电力通过输电线路传递的中继点。

Initially, all \(K\) power plants are operational, but it is not guaranteed that all factories can secure the necessary power even in the initial state.
初始时，所有 \(K\) 个发电厂都在运行，但无法保证即使在初始状态下所有工厂都能获得必要的电力。

However, due to aging, power plants are expected to fail and shut down sequentially. Specifically, \(Q\) events occur in order. At each event \(t\) (\(1 \leq t \leq Q\)), power plant \(S_t\) fails and becomes non-operational. Once a power plant fails, it remains non-operational permanently. Note that \(Q \leq K\), and not all power plants necessarily fail.
然而，由于老化，发电厂预计会依次故障并停机。具体来说，按顺序发生 \(Q\) 个事件。在每个事件 \(t\)（\(1 \leq t \leq Q\)），发电厂 \(S_t\) 发生故障并变为非运行。一旦发电厂故障，它将永久保持非运行状态。注意，\(Q \leq K\)，且并非所有发电厂都必然故障。

For the state immediately after each event occurs, determine whether all factories can secure the necessary power and continue operating. That is, after each event, answer whether there exists a way to route power such that, using only the currently operational power plants, the flow conservation conditions are satisfied and at least \(B_i\) megawatts of power is delivered to each factory \(i\).
对于每个事件发生后的即时状态，判断所有工厂是否能够获得必要的电力并继续运营。也就是说，在每个事件后，回答是否存在一种电力路由方式，使得仅使用当前运行的发电厂，满足流量守恒条件，并且每个工厂 \(i\) 获得至少 \(B_i\) 兆瓦的电力。

【输入】

\(N\) \(K\) \(M\)
\(B_1\) \(B_2\) \(\ldots\) \(B_N\)
\(W_1\) \(W_2\) \(\ldots\) \(W_K\)
\(U_1\) \(V_1\) \(C_1\)
\(U_2\) \(V_2\) \(C_2\)
\(\vdots\)
\(U_M\) \(V_M\) \(C_M\)
\(Q\)
\(S_1\)
\(S_2\)
\(\vdots\)
\(S_Q\)

• The first line contains the number of factories \(N\), the number of power plants \(K\), and the number of transmission lines \(M\), separated by spaces.
• The second line contains the daily power requirements \(B_1, B_2, \ldots, B_N\) of each factory, separated by spaces. Factory \(i\) corresponds to location \(i\).
• The third line contains the maximum daily supply \(W_1, W_2, \ldots, W_K\) of each power plant, separated by spaces. Power plant \(k\) corresponds to location \(N + k\).
• The following \(M\) lines, where the \(j\)-th line (\(1 \leq j \leq M\)), contains the locations \(U_j\), \(V_j\) connected by transmission line \(j\), and the maximum transmission capacity \(C_j\), separated by spaces. Each transmission line is bidirectional (undirected edge), and is given with \(U_j < V_j\).
• The next line contains the number of events \(Q\).
• The following \(Q\) lines, where the \(t\)-th line (\(1 \leq t \leq Q\)), contains the number \(S_t\) (\(1 \leq S_t \leq K\)) of the power plant that fails in event \(t\). Power plant \(S_t\) corresponds to location \(N + S_t\).

【输出】

Output \(Q\) lines. The \(t\)-th line (\(1 \leq t \leq Q\)) should contain Yes if all factories can secure the necessary power immediately after event \(t\) occurs, and No otherwise.

【输入样例】

2 2 3
2 3
2 5
1 3 2
1 4 2
2 4 3
2
1
2

【输出样例】

Yes
No

【核心思想】

1. 问题分析：给定 \(N\) 个工厂（需求 \(B_i\)）、\(K\) 个发电厂（供应 \(W_k\)）和 \(M\) 条输电线路（容量 \(C_j\)），需要判断每次发电厂故障后，剩余运行的发电厂是否能满足所有工厂的电力需求。这是一个多源点多汇点网络流问题，需要判断最大流是否不小于总需求。

2. 算法选择：

   • Dinic算法：基于分层图和多路增广的最大流算法，时间复杂度较优
   • 超级源汇点技巧：添加超级源点 \(ss\) 连接所有运行中的发电厂，添加超级汇点 \(tt\) 连接所有工厂，转化为单源单汇最大流问题

3. 关键步骤：

   • 计算总需求量 \(need = \sum_{i=1}^{N} B_i\)
   • 对每个事件（发电厂 \(S_t\) 故障）：
     • 标记该发电厂为失效状态 \(alive[S_t] = false\)
     • 重新构建网络流图：
       • 超级源点 \(ss\) 向每个运行的发电厂 \(k\) 连边，容量 \(W_k\)
       • 每个工厂 \(i\) 向超级汇点 \(tt\) 连边，容量 \(B_i\)
       • 原输电线路 \((U_j, V_j)\) 双向连边，容量 \(C_j\)
     • 运行 Dinic 算法计算最大流 \(flow\)
     • 若 \(flow \geq need\)，输出 Yes；否则输出 No

4. 时间/空间复杂度：

   • 时间复杂度：\(O(Q \cdot M \cdot \sqrt{N+K})\)，每次事件重新建图并运行 Dinic，实际复杂度为 \(O(Q \cdot E \cdot \sqrt{V})\) 或更优
   • 空间复杂度：\(O(N + K + M)\)，存储网络流图、层次数组和当前弧数组

5. 网络流建模的核心思想：

   • 多源多汇转化：通过超级源汇点将复杂问题标准化为单源单汇最大流
   • 供应侧建模：源点 → 发电厂 → 输电网络，容量限制供应和传输
   • 需求侧建模：工厂 → 汇点，容量表示最低需求
   • 可行性判定：最大流 ≥ 总需求时，存在满足条件的电力分配方案
   • 适用于资源分配、供应链、交通网络等场景

【解题思路】

【算法标签】

网络流

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100, M = 1000;int n, k, m, q;
int B[N], W[N], S[N];  // B: 需求, W: 供应, S: 要移除的供应商
int h[N], e[M], w[M], ne[M], idx = 2;  // 网络流相关数组
int d[N], cur[N];
bool alive[N];  // 标记供应商是否存活
int ss, tt;  // 超级源点和超级汇点
struct Edge
{int u, v, c;
} edges[M];  // 存储原图中的边// 添加网络流边
void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}// BFS构建层次图
bool bfs()
{memset(d, 0, sizeof(d));queue<int> q;q.push(ss);d[ss] = 1;while (q.size()){int u = q.front();q.pop();for (int i = h[u]; i != -1; i = ne[i]){int v = e[i];if (d[v] == 0 && w[i])  // 如果未访问且边有容量{d[v] = d[u] + 1;q.push(v);if (v == tt){return true;  // 到达汇点}}}}return false;  // 无法到达汇点
}// DFS进行多路增广
int dfs(int u, int mf)
{if (u == tt){return mf;  // 到达汇点}int sum = 0;for (int i = cur[u]; i != -1; i = ne[i]){cur[u] = i;  // 当前弧优化int v = e[i];if (d[v] == d[u] + 1 && w[i])  // 满足层次关系和容量限制{int f = dfs(v, min(mf, w[i]));w[i] -= f;     // 正向边减少容量w[i ^ 1] += f; // 反向边增加容量sum += f;mf -= f;if (mf == 0){break;  // 流量已用完}}}if (sum == 0){d[u] = 0;  // 残量网络中u不可达}return sum;
}// Dinic算法计算最大流
int dinic()
{int flow = 0;while (bfs())  // 每次构建新的层次图{memcpy(cur, h, sizeof(h));  // 重置当前弧flow += dfs(ss, 1e18);}return flow;
}signed main()
{cin >> n >> k >> m;int need = 0;  // 总需求量for (int i = 1; i <= n; i++){cin >> B[i];need += B[i];  // 累加总需求}for (int i = 1; i <= k; i++){cin >> W[i];}for (int i = 1; i <= m; i++){cin >> edges[i].u >> edges[i].v >> edges[i].c;  // 读取原图中的边}cin >> q;for (int i = 1; i <= q; i++){cin >> S[i];  // 读取要移除的供应商}memset(alive, true, sizeof(alive));  // 初始化所有供应商为存活状态// 处理每个查询for (int i = 1; i <= q; i++){alive[S[i]] = false;  // 标记该供应商为移除状态// 重新建图memset(h, -1, sizeof(h));idx = 2;ss = 0, tt = n + k + 1;  // 超级源点和超级汇点// 连接任务到汇点for (int i = 1; i <= n; i++){add(i, tt, B[i]);  // 任务i到汇点，容量为需求量add(tt, i, 0);     // 反向边}// 连接源点到存活的供应商for (int i = 1; i <= k; i++){if (alive[i]){add(ss, n + i, W[i]);  // 源点到供应商，容量为供应量add(n + i, ss, 0);     // 反向边}}// 添加原始图中的边（双向容量）for (int i = 1; i <= m; i++){int u = edges[i].u, v = edges[i].v, c = edges[i].c;add(u, v, c);add(v, u, 0);add(v, u, c);add(u, v, 0);}int flow = dinic();  // 计算最大流if (flow >= need)    // 检查是否满足所有需求{cout << "Yes" << endl;}else{cout << "No" << endl;}}return 0;
}

【运行结果】

2 2 3
2 3
2 5
1 3 2
1 4 2
2 4 3
2
1
Yes
2
No