分数: 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