CF2275G.Copper Squander
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
K1o0n accepted an alternative ending and got a job in the programming department. As is known, all programmers know how to dig trenches for cables, so his very first assignment was wiring between the university buildings — with the happy right to sell off the old stuff on his own.
There are n buildings at the university, and cables are laid between some pairs of them — m cables in total. Data travels in both directions along the i-th cable; it connects buildings ui and vi, and it contains copper worth di coins. The network was laid long before K1o0n, and nobody cared about money: somewhere an extra jumper was installed, somewhere a more expensive cable was used, and some buildings were never reached at all.
The network can be rebuilt in exactly the following order:
- Remove any subset of cables. The copper from the removed i-th cable is sent to a recycling center and brings di coins; there is no longer any connection through that cable.
- Lay any number of new cables between any two distinct buildings. K1o0n digs the trenches himself, but the cable is installed by a construction crew, and its appetite grows with every request: the first new cable will cost x coins, the second — 2x, the third — 3x, and so on.
After that, the network must be connected: data must be able to travel from any building to any other building. Note that initially the network may be disconnected.
Profit is the revenue from sold copper minus the installation costs.
You are given q scenarios, in the j-th scenario the installation cost increment is xj. For each scenario, find the maximum possible profit.
K1o0n 接受了一个替代结局,并入职了编程部门。众所周知,所有程序员都懂得如何挖掘电缆沟槽,因此他的第一项任务就是为大学各栋建筑之间铺设网络线缆——同时享有自行处置旧设备并出售牟利的“幸福权利”。
大学共有 n 栋建筑,其中某些建筑对之间已铺设了电缆,总计 m 条电缆。第 i 条电缆为双向通信链路,连接建筑 ui 和 vi,其内部铜材价值 di 枚金币。该网络早在 K1o0n 入职前就已建成,当时无人关注成本:某些地方安装了冗余跳线,某些地方使用了更昂贵的电缆,甚至还有些建筑压根未被接入网络。
网络可按如下方式重建:
- 移除任意子集的现有电缆。移除第 i 条电缆后,其铜材将送至回收中心,带来 di 枚金币收入;该电缆所对应的连接亦随之消失。
- 在任意两栋不同建筑之间铺设任意数量的新电缆。K1o0n 亲自挖掘沟槽,但电缆安装由施工队完成,而施工队的要价随每次请求递增:第一条新电缆花费 x 枚金币,第二条花费 2x 枚金币,第三条花费 3x 枚金币,依此类推。
重建完成后,整个网络必须是连通的:即任意一栋建筑均能通过电缆路径到达其他任意一栋建筑。(注意:初始网络可能并不连通。)
利润定义为:出售铜材所得收入减去新电缆安装总成本。
现给出 q 个场景,其中第 j 个场景中新电缆单位成本增量为 xj。对每个场景,请计算所能获得的最大利润。
输入格式
The first line contains one integer t (1≤t≤104) — the number of testcases.
The first line of each testcase contains three integers n, m, and q (2≤n≤105, 0≤m≤2⋅105, 1≤q≤2⋅105) — the number of buildings, cables, and scenarios.
The next m lines contain three integers each: ui, vi, and di (1≤ui,vi≤n, ui=vi, 1≤di≤5⋅108) — the endpoints of the i-th cable and the value of the copper in it. A cable cannot connect a building to itself, and no pair of buildings is connected by two cables.
The last line of the testcase contains q integers x1,x2,…,xq (1≤xj≤5⋅108) — the installation cost increments in the scenarios.
It is guaranteed that the sum of n over all testcases does not exceed 105, the sum of m does not exceed 2⋅105, and the sum of q does not exceed 2⋅105.
第一行包含一个整数 t(1≤t≤104)——测试用例的数量。
每个测试用例的第一行包含三个整数 n、m 和 q(2≤n≤105,0≤m≤2⋅105,1≤q≤2⋅105)——分别表示建筑物数量、电缆数量和场景数量。
接下来的 m 行每行包含三个整数:ui、vi 和 di(1≤ui,vi≤n,ui=vi,1≤di≤5⋅108)——表示第 i 条电缆的两个端点及其所含铜的价值。一条电缆不能连接同一座建筑物,且任意两座建筑物之间至多只有一条电缆。
每个测试用例的最后一行包含 q 个整数 x1,x2,…,xq(1≤xj≤5⋅108)——表示各场景中的安装成本增量。
保证所有测试用例中 n 的总和不超过 105,m 的总和不超过 2⋅105,q 的总和不超过 2⋅105。
输出格式
For each scenario, output one integer — the maximum profit. Print the answers for the scenarios of one testcase in the same order as the scenarios are given, on one line.
对于每种情况,输出一个整数——最大利润。在同一行中按题目给出的情况顺序输出该测试用例中各情况的答案。
输入输出样例
输入#1
3 4 4 1 1 2 1 2 3 1 3 4 1 1 4 10 1 5 4 1 1 2 5 1 3 5 1 4 5 1 5 5 1 5 4 3 1 2 5 2 3 5 3 4 5 1 3 1 1 3 10
输出#1
10 10 9 2 -5
说明/提示
null
输入解题思路,AI测评打分。不知道怎么写?