UOJ Logo Universal Online Judge

UOJ

#108. 【APIO2013】TOLL

附件下载 统计

幸福国度可以用 $N$ 个城镇(用 $1$ 到 $N$ 编号)构成的集合来描述,这些城镇最开始由 $M$ 条双向道路(用 $1$ 到 $M$ 编号)连接。城镇 $1$ 是中央城镇。保证一个人从城镇 $1$ 出发,经过这些道路,可以到达其他的任何一个城市。这些道路都是收费道路,道路 $i$ 的使用者必须向道路的主人支付 $c_i$ 分钱的费用。已知所有的这些 $c_i$ 是互不相等的。最近有 $K$ 条新道路建成,这些道路都属于亿万富豪 Mr. Greedy。

Mr. Greedy 可以决定每条新道路的费用(费用可以相同),并且他必须在明天宣布这些费用。

两周以后,幸福国度将举办一个盛况空前的嘉年华!大量的参与者将沿着这些道路游行并前往中央城镇。共计 $p_j$ 个参与者将从城镇 $j$ 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行,并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗,这些道路将由幸福国度中最有钱的人选出,也就是 Mr. Greedy。同样根据这个习俗,Mr. Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小,并且仍要保证任何人可以从城镇 $j$ 前往城镇 $1$ (因此,这些选出的道路来自将费用作为相应边边权的 “最小生成树”)。如果有多个这样的道路集合,Mr. Greedy 可以选其中的任何一个,只要满足费用和是最小的。

Mr. Greedy 很明确地知道,他从 $K$ 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲,如果 $p$ 个人经过道路 $i$,道路 $i$ 产生的收入为乘积 $c_i \cdot p$。注意 Mr. Greedy 只能从新道路收取费用,因为原来的道路都不属于他。

Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用(将在明天公布),并且选择嘉年华用的道路(将在嘉年华的前一天公布),使得他在 $K$ 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

你是一个记者,你想揭露他的计划。为了做成这件事,你必须先写一个程序来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。

输入格式

第一行包含三个由空格隔开的正整数 $N,M$ 和 $K$。

接下来的 $M$ 行描述最开始的 $M$ 条道路。这 $M$ 行中的第 $i$ 行包含由空格隔开的整数 $a_i, b_i, c_i$,表示有一条在 $a_i$ 和 $b_i$ 之间,费用为 $c_i$ 的双向道路。保证 $1 \leq a_i, b_i \leq N$。保证如果 $i \neq i'$,则 $c_i \neq c_{i'}$。

接下来的 $K$ 行描述新建的 $K$ 条道路。这 $K$ 行中的第 $i$ 行包含由空格隔开的整数 $x_i$ 和 $y_i$,表示有一条连接城镇 $x_i$ 和 $y_i$ 新道路。保证 $1 \leq x_i, y_i \leq n$。

最后一行包含 $N$ 个由空格隔开的整数,其中的第 $j$ 个为 $p_j$,表示从城镇 $j$ 前往城镇 $1$ 的人数。

保证在任意两个城市之间,最多只有一条道路(包括新建的道路)。

输出格式

你的程序必须输出恰好一个整数到标准输出,表示能获得的最大的收入。

样例一

input

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

output

400

explanation

Mr. Greedy 应该将新道路 $(1,3)$ 的费用设置为 $5$ 分钱。在这个费用下,他可以选择道路 $(3,5),(1,2),(2,4)$ 和 $(1,3)$ 来最小化总费用,这个费用为 $14$。

从城镇 $3$ 出发的 $30$ 个人和从城镇 $5$ 出发的 $50$ 个人将经过新道路前往城镇 $1$,因此他可以获得为 $(30+50) \times 5=400$ 分钱的最好收入。

如果我们这样做,将新道路 $(1,3)$ 的费用设置为 $10$ 分钱。根据传统的限制,Mr. Greedy 必须选择 $(3,5),(1,2),(2,4)$ 和 $(2,3)$,因为这是唯一费用最小的集合。

因此,在嘉年华的过程中道路 $(1,3)$ 将没有任何收入。

限制与约定

我们将使用以下 5 类测例测试你的程序。

对每个 $i$ 和 $j$,$1 \leq c_i, p_j \leq 10^6$。

  1. ($16$ 分) $N \leq 10, M \leq 20$ 且 $K = 1$;
  2. ($18$ 分) $N \leq 30, M \leq 50$ 且 $K \leq 10$;
  3. ($22$ 分) $N \leq 1000, M \leq 5000$ 且 $K \leq 10$;
  4. ($22$ 分) $N \leq 100000, M \leq 300000$ 且 $K \leq 15$;
  5. ($22$ 分) $N \leq 100000, M \leq 300000$ 且 $K \leq 20$。

时间限制:$3\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载