[OII 2025] 路灯收集 / Raccogli i lampioni - 题目

内存限制：512 MiB 时间限制：2000 ms 标准输入输出

题目类型：VJudge（洛谷）评测方式：VJudge

上传者：匿名

提交提交记录统计讨论题解

译自 Italian Olympiad in Informatics (OII) 2025 - Raccogli i lampioni。

OII 纪念碑的建造场地终于被清理干净了！工作人员现在需要考虑的是该区域的照明工作。购买新的路灯是不可能的，因为大部分资金都花在了木材运输上。一个更现实的方案是从乌迪内市借用一些路灯。

乌迪内市有个路口，被条双向道路所连接。在路口，有一盏高度为的路灯。第条道路连接编号为和的路口，长度为。

要借用一盏路灯，必须将其放倒在一条连接了路口的道路上，前提是这条路上要有足够的空间：也就是说，放倒在第条道路上的路灯长度之和不能超过。

请帮助工作人员确定能借用的最大路灯数量。

两个路口之间可能有多于一条道路。此外，不能保证每个路口都可以通过道路与其他所有路口相连。

实现细节

附件中包含一个实现示例 benilluminato.cpp。

你需要实现如下函数：

int illumina(int N, int M, vector<int> H, vector<int> A, vector<int> B, vector<int> L);

整数：路口的数量。
整数：道路的数量。
数组：下标从到，包含每个路口上路灯的高度。
数组和：下标从到，描述了道路，其中第条道路连接路口和，长度为米。
该函数需要返回能借用的最大路灯数量。
对于每个测试点，该函数都只会被调用一次。

评测程序的输入格式如下：

第行：两个整数和。
第行：个整数。
第行（）：三个整数。

评测程序的输出格式如下：

输出一行一个整数，表示函数 illumina 的返回值。

样例输入 1

样例输出 1

样例输入 2

8 10
3 2 3 2 4 6 5 9
0 1 4
1 2 1
2 3 3
3 4 1
0 4 8
2 5 8
3 5 7
1 6 4
5 7 3
6 7 10

样例输出 2

样例输入 3

样例输出 3

【样例解释】

在样例 1 中，如下的方案可以最大化借用的路灯数量（可以借用所有路灯）：

将路灯和路灯放倒在道路上；
将路灯放倒在道路上；
将路灯放倒在道路上。

在样例 2 中，如下的方案可以最大化借用的路灯数量（不能借用所有的盏路灯，但是可以借用盏）：

将路灯和路灯放倒在道路上；
将路灯放倒在道路上；
将路灯放倒在道路上；
将路灯放倒在道路上；
将路灯放倒在道路上；
将路灯放倒在道路上。

在样例 3 中，如下的方案可以最大化借用的路灯数量（可以借用所有路灯）：

将路灯放倒在道路上；
将路灯放倒在道路上。

【数据范围】

；
；
且；
。

【子任务】

子任务编号	分值	约束条件
		样例

		，，且
		，，
		且

		无额外限制

编辑器加载中 …

或者，上传代码文件

Powered by SYZOJ. Modified by Zemu (UnratedCheater).

项目源码 · 陶片放逐 · 新ICP备2026003452号-2

当前版本：V1.7.2-premium

#214539. [OII 2025] 路灯收集 / Raccogli i lampioni

题目描述