AdditionalFile6998.zip

#6998. 「THUPC 2026 初赛」Unpair Ampere

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目背景

K 市地处暖流与山地之间，得天独厚的气象条件使得该市传统手工艺发达。受水汽影响，该市年平均日照时数低于全国平均水平，故其供电长期以火力发电为主。另外，深厚的历史底蕴使得文化观光旅游产业成为 K 市重要支柱产业，大范围设置太阳能光伏板可能会影响旅游景观的观赏效果。随着以光伏发电为代表的太阳能发电系统的成本不断降低，该市决定将部分高耗低效的火力发电落后产能替换为太阳能发电，从而更好地实现节能减排、绿色低碳的发展目标。

尽管有些发怵，也应迈出一步。若是原地踌躇，徒把光阴虚度。为了改变明天，无悔选择作出。

题目描述

K 市的输电网络可以被视作一张 $N$ 个结点 $M$ 条边的有向无环图，其中每个没有入度的结点表示一座正在运行中的火力发电厂；其余有入度的各结点分别表示需要输送电力的设施，第 $i$ 座设施的用电负荷峰值为 $a_{i}$ 安培。作为 K 市电网的运营主体，Spark公司计划将部分火力发电厂临时改造为太阳能发电厂，进行联网试运行。

记 $S_{y}$ 表示由在试运行期间维持原有火力发电厂正常输出的结点所组成的集合，$S_{z}$为 Spark 临时改造成太阳能发电厂的结点集合。Spark 公司原先已经确定了一种临时改造方案，但在配置设备时发觉该方案可能容易引起大面积故障。具体而言，在试运行期间，可能存在一些设施直接或间接地同时连接到 $S_{y}$ 和 $S_{z}$ ，由两种迥异的发电厂同时供电，从而显著地增加了引发供电耦合异常等突发事件的风险。然而，由于日程较为紧张， Spark 公司不能从头设计方案、部署设备。

为了尽量减少在试运行期间对 K 市生产生活秩序带来的影响，Spark 公司希望在原有方案的基础上研制一种尽可能隔离两种供电类型的紧急转换方案，使得 K 市电网总风险最小。换句话说，Spark 需要最小化同时连接到 $S_{y}$ 和 $S_{z}$ 的用电设施的负荷峰值 $a_{i}$之和，与紧急将部分发电厂转换为另一种发电类型时带来的发电量损失（同样由 $a_{i}$ 表示）的总和。为了更好地确定是否需要采取紧急转换方案，Spark 暂定转换后 $S_{y}$ 或 $S_{z}$可以为空。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $N, M$ ，表示 K 市输电网络的结点数量和直接相连的输电线路的数量。保证 $2 \leq N \leq 5,000,1 \leq M \leq \min \{50,000, N(N-1) / 2\}$。

输入的第二行包含 $N$ 个整数 $d_{1}, \cdots, d_{N}$ ，表示各结点的类型：如果 $d_{i}=-1$ ，则结点 $i$ 为用电设施；否则，结点 $i$ 为发电厂，且 $d_{i}=0$ 当且仅当在原始改造方案中结点 $i$仍为火力发电厂 $\left(i \in S_{y}\right)$，而 $d_{i}=1$ 当且仅当在原始改造方案中结点 $i$ 应临时被改造为太阳能发电厂（$i \in S_{z}$）。保证 $-1 \leq d_{i} \leq 1$ ，且输入中至少有一个 $d_{i}=1$。

输入的第三行包含 $N$ 个正整数 $a_{1}, \cdots, a_{N}$，表示各用电设施结点的用电负荷峰值，或各发电厂紧急转换发电类型时带来的发电量损失（单位：安培）。保证 $1 \leq a_{i} \leq 40$。

接下来 $M$ 行，每行输入两个正整数 $u_{i}, v_{i}$，表示电网中有一条输电线路直接从 $u_{i}$ 向 $v_{i}$ 输送电力。保证 $1 \leq u_{i}, v_{i} \leq N$，输入不包含重边，且输入的图是至少有 $2$ 个入度为 $0$ 的结点的有向无环图。

输出格式

输出到标准输出。

输出一个非负整数，表示最优紧急转换方案的总风险（单位：安培）。

样例 1

输入

6 6
0 1 0 1 -1 -1
11 17 1 13 2 28
1 5
2 5
3 5
2 6
3 6
4 6

输出

3

样例 2

输入

6 7
0 1 0 -1 -1 -1
11 17 1 13 2 28
1 4
2 4
2 5
2 6
3 5
4 6
5 6

输出

12

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。