← 返回题目列表

AtCoder · awc0031_e

E. 电网停电危机

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥管理着某个地区的供电系统。该地区有 N 工厂和 K 发电厂,通过输电线路连接形成输电网络。

位置编号为 1 to N + K,位置 1 通过 N 对应工厂和地点 N + 1 通过 N + K 对应于发电厂。具体来说,工厂 i (1 \leq i \leq N) 位于以下位置 i和发电厂 k (1 \leq k \leq K) 位于以下位置 N + k.

传输网络包括 N + K 位置由以下连接 M 传输线。每条传输线 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.

各电厂 k (1 \leq k \leq K),在运行时,可以提供之间的任意电量 0 和 W_k 每天兆瓦。各工厂 i (1 \leq i \leq N) 至少需要接收 B_i 每天运行的电力为兆瓦。工厂可能会收到超过 B_i 兆瓦功率;即使有多余电力流入,它也可以正常运行。

在每个位置,流量守恒必须保持以实现功率平衡。的 净流入 \mathrm{net}(v) 位于位置 v 定义如下:

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

澄清这个公式的含义:对于传输线 j,当 f_j > 0,功率来自 U_j to V_j,所以 f_j 流入位置 V_j 和 f_j 流出位置 U_j。当 f_j < 0,反之亦然。 \mathrm{net}(v) 等于该位置的总流入量 v 减去位置的总流出量 v,对连接到位置的所有传输线路求和 v.

每个地点必须满足以下条件:

  • 如果位置 v 是工厂 i: \mathrm{net}(v) \geq B_i。也就是说,至少净流入 B_i 兆瓦必须流入工厂 i 通过传输线。
  • 如果位置 v 是一个 运行 发电厂 k: -W_k \leq \mathrm{net}(v) \leq 0。也就是发电厂 k 可以供应之间 0 和 W_k 兆瓦功率。由于所提供的电力离开该位置,因此净流入为负。
  • 如果位置 v 是 不可操作 发电厂: \mathrm{net}(v) = 0。它不能供电,但只要流入等于流出,它仍然可以充当电力通过传输线传递的中继点。

最初,所有 K 发电厂已投入运行,但即使在初始状态下,也不能保证所有工厂都能获得必要的电力。

然而,由于老化,预计发电厂将相继出现故障并关闭。具体来说, Q 事件按顺序发生。在每次活动中 t (1 \leq t \leq Q),发电厂 S_t 失败并变得不可操作。一旦发电厂发生故障,它将永久停止运行。请注意 Q \leq K,并且并非所有发电厂都一定会发生故障。

对于每个事件发生后的状态,确定所有工厂是否能够获得必要的电力并继续运营。也就是说,在每个事件之后,回答是否存在一种方式来路由电力,使得仅使用当前运行的发电厂,满足流量守恒条件并且至少 B_i 向每个工厂输送兆瓦电力 i.

约束

  • 1 \leq N \leq 32
  • 1 \leq K \leq 32
  • 0 \leq M \leq 300
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq W_k \leq 10^9 (1 \leq k \leq K)
  • 1 \leq U_j < V_j \leq N + K (1 \leq j \leq M)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • 任意一对位置之间至多有一条传输线(不存在多边)
  • 1 \leq Q \leq K
  • 1 \leq S_t \leq K (1 \leq t \leq Q)
  • S_1, S_2, \ldots, S_Q 都是不同的(没有发电厂发生多次故障)
  • 所有输入值均为整数

输入

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
  • 第一行包含工厂数量 N, 发电厂数量 K,以及传输线的数量 M,用空格分隔。
  • 第二行包含日常电量需求 每个工厂的 B_1, B_2, \ldots, B_N ,以空格分隔。工厂 i 对应位置 i.
  • 第三行包含每日最大供应量 每个发电厂的 W_1, W_2, \ldots, W_K ,以空格分隔。发电厂 k 对应位置 N + k.
  • 以下 M 行,其中 j第行(1 \leq j \leq M),包含位置 U_j, V_j 通过传输线连接 j,以及最大传输容量 C_j,用空格分隔。每条传输线都是双向的(无向边),并由下式给出 U_j < V_j.
  • 下一行包含事件数 Q.
  • 以下 Q 行,其中 t第行(1 \leq t \leq Q),包含数字 S_t (1 \leq S_t \leq K) 发生故障的发电厂 t。发电厂 S_t 对应位置 N + S_t.

输出

输出 Q 行。的 t第行(1 \leq t \leq Q) 应包含 Yes 如果所有工厂都能在事件发生后立即获得必要的电力 t 发生,并且 No 否则。


示例输入 1

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

示例输出 1

Yes
No

示例输入 2

2 2 3
3 3
6 6
1 2 2
1 3 6
2 4 3
1
2

示例输出 2

No

示例输入 3

4 3 10
3 4 2 5
7 4 7
1 5 3
2 5 4
1 6 3
3 6 2
4 6 2
2 7 3
3 7 3
4 7 5
5 6 4
6 7 4
3
2
1
3

示例输出 3

Yes
No
No

示例输入 4

6 5 19
2 4 3 5 4 3
5 4 6 7 8
1 7 3
1 9 2
2 7 4
2 10 2
3 8 3
3 9 3
4 10 5
4 11 3
5 8 2
5 11 4
6 9 2
6 11 3
7 8 3
8 9 3
9 10 3
10 11 3
7 9 4
7 10 4
8 11 2
4
2
1
5
4

示例输出 4

Yes
Yes
No
No

示例输入 5

1 1 0
1
1
1
1

示例输出 5

No