[APIO2013] 道路费用
题目描述
幸福国度可以用 N 个城镇(用 1 到 N 编号)构成的集合来描述,这些城镇 最开始由 M 条双向道路(用 1 到 M 编号)连接。城镇 1 是中央城镇。保证一个 人从城镇 1 出发,经过这些道路,可以到达其他的任何一个城市。这些道路都是 收费道路,道路 i 的使用者必须向道路的主人支付 ci分钱的费用。已知所有的这 些ci是互不相等的。最近有K条新道路建成,这些道路都属于亿万富豪Mr. Greedy。 Mr. Greedy 可以决定每条新道路的费用(费用可以相同),并且他必须在明天宣 布这些费用。
两周以后,幸福国度将举办一个盛况空前的嘉年华!大量的参与者将沿着这 些道路游行并前往中央城镇。共计 pj个参与者将从城镇 j 出发前往中央城镇。这 些人只会沿着一个选出的道路集合前行,并且这些选出的道路将在这件事的前一 天公布。根据一个古老的习俗,这些道路将由幸福国度中最有钱的人选出,也就 是 Mr. Greedy。同样根据这个习俗,Mr. Greedy 选出的这个道路集合必须使所有 选出道路的费用之和最小,并且仍要保证任何人可以从城镇 j 前往城镇 1(因此, 这些选出的道路来自将费用作为相应边边权的“最小生成树”)。如果有多个这样 的道路集合,Mr. Greedy 可以选其中的任何一个,只要满足费用和是最小的。
Mr. Greedy 很明确地知道,他从 K 条新道路中获得的收入不只是与费用有 关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲,如果 p 个人经过道路 i,道路 i 产生的收入为 ci p 的积。注意 Mr. Greedy 只能从新道路 收取费用,因为原来的道路都不属于他。
Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收 入。他希望指定每条新道路的费用(将在明天公布),并且选择嘉年华用的道路 (将在嘉年华的前一天公布),使得他在 K 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。
你是一个记者,你想揭露他的计划。为了做成这件事,你必须先写一个程序 来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。
输入输出格式
输入格式
你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数 N,M 和 K。接下来的 M 行描述最开始的 M 条道路。这 M 行中的第 i 行包含由空格隔开 的整数 ai,bi和 ci,表示有一条在 ai 和 bi之间,费用为 ci 的双向道路。接下来的 K 行描述新建的 K 条道路。这 K 行中的第 i 行包含由空格隔开的整数 xi和 yi,表 示有一条连接城镇 xi 和 yi 新道路。最后一行包含 N 个由空格隔开的整数,其中 的第 j 个为 pj,表示从城镇 j 前往城镇 1 的人数。
输入也满足以下约束条件。
1 ≤ N ≤ 100000;
1 ≤ K ≤ 20;
1 ≤ M ≤ 300000;
对每个 i 和 j,1 ≤ ci, pj ≤ 10^6;
如果 i ≠ i',则 ci ≠ ci';
在任意两个城市之间,最多只有一条道路(包括新建的道路)。
输出格式
你的程序必须输出恰好一个整数到标准输出,表示能获得的最大的收入。
输入输出样例
输入样例 #1
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
输出样例 #1
400
说明
在样例中,Mr. Greedy 应该将新道路(1,3)的费用设置为 5 分钱。在这个费用 下,他可以选择道路(3,5),(1,2),(2,4)和(1,3)来最小化总费用,这个费用为 14。 从城镇 3 出发的 30 个人和从城镇 5 出发的 50 个人将经过新道路前往城镇 1,因 此他可以获得为(30+50)×5=400 分钱的最好收入。
如果我们这样做,将新道路(1,3)的费用设置为 10 分钱。根据传统的限制, Mr. Greedy 必须选择(3,5),(1,2),(2,4)和(2,3),因为这是唯一费用最小的集合。 因此,在嘉年华的过程中道路(1,3)将没有任何收入。
我们将使用以下 5 类测例测试你的程序。
1. (国际 16 分,国内 15 分)N ≤ 10,M ≤ 20 且 K = 1;
2. (国际 18 分,国内 20 分)N ≤ 30,M ≤ 50 且 K ≤ 10;
3. (国际 22 分,国内 20 分)N ≤ 1,000,M ≤ 5,000 且 K ≤ 10;
4. (国际 22 分,国内 20 分)N ≤ 100,000,M ≤ 300,000 且 K ≤ 15;
5. (国际 22 分,国内 25 分)N ≤ 100,000,M ≤ 300,000 且 K ≤ 20。
**update: 2024/07/04 删除了两个测试点,并且改为捆绑。**