#1937. Storm

Storm

Storm

题目描述

标题: Storm - Problem - QOJ.ac

#13461. Storm

Statistics

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