#1937. Storm
Storm
Storm
题目描述
标题: Storm - Problem - QOJ.ac
#13461. Storm
The problem was used in the following contests:
题目背景
风暴席卷了见泷原市。
市气象局还未来得及建立起任何监测设施,要想确定风暴的状态,只能借助市内的风力计数据。而这项任务被交给了你——气象局新聘任的一名数据工程师。
题目描述
城市中有 M 条主要街道,它们连接着 N 个路口。在每个路口处都有一个风力计,其中路口 i 处的风力计示数为 vi ,示数越大表示风力越强。
在街道中可能出现"狭管效应",即气流经过狭窄的区域时压强降低、流速升高的现象。这会导致穿过该街道的风速提高,从而使得该街道连接的路口处风力计示数相比真实值偏大。第 i 条街道的该效应强度为 ei 。
为了确定风暴中心地带的范围,你需要找到一个由不超过 K 条街道(可以是 0 条,另外注意不能重复选择一条街道)组成的集合 S ,以最大化:
(1)∑x∈I(S)vx−∑y∈Sey
其中 I(S) 表示所有与 S 中至少一条街道相连的路口构成的集合。
如果一个路口与超过一条 S 中的街道相连,它也只会被算入一次。气象专家猜测风暴的外围可能存在多个较小的气旋,从而可能存在多个独立的风暴中心,因此你选出的街道集合不一定连通。
请你尽快完成任务,气象局能否采取下一步行动取决于你的表现。
输入格式
第一行一个正整数 T ,表示测试点个数。接下来对每个测试点:
- 第一行三个正整数 N,M,K ,分别表示路口个数、街道条数、选取街道数量的上限。路口按 1 到 N 标号,街道按 1 到 M 标号。
- 第二行 N 个非负整数,表示 v1,v2,⋯,vN 。
- 接下来 M 行,其中的第 i 行有三个整数 ai,bi,ei ,表示街道 i 连接路口 ai 与 bi ,其狭管效应强度为 ei 。
输出格式
对每个测试点输出一行一个整数,表示 (1) 式的最大值。
样例数据
样例 1 输入
1
5 5 2
1 2 4 8 16
1 2 1
1 3 2
3 4 2
4 5 2
2 5 1
样例 1 输出
27
样例 1 解释
集合 S 应包含街道 (2,5) 和街道 (3,4) ,其 ei 值之和为 3 。此时 I(S) 包含结点 2,3,4,5 ,其 vi 值之和为 30 。
子任务
对所有数据:
- ∑2K(N+M)≤106 ,这里的求和号表示对一组数据中所有测试点求和。
- 1≤T≤5
- 1≤N,M,K
- 0≤ei,vi≤108
- 1≤ai,bi≤N
- 所有路口和街道所构成的无向图没有自环,但可以有重边、可以不连通、可以有孤立点。
- 保证答案不超过 2⋅109 。
子任务 1:30 分,∑(N+M)≤1500
子任务 2:30 分,K≤9
子任务 3:40 分,无额外限制
后记
在埋头调试的间隙,你抬头望了望窗外,迎面晃眼的阳光却让你一愣。
不知何时,风暴已经停息了。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1
5 5 2
1 2 4 8 16
1 2 1
1 3 2
3 4 2
4 5 2
2 5 1
27