← 返回题目列表

Codeforces · 1023/F

F. 手机网络

中文机器翻译题面 查看原题

您正在管理移动电话网络,并希望提供有竞争力的价格来连接网络。

网络有 $$$n$$$ 个节点。

您的竞争对手已经在某些节点之间提供了一些连接,并且价格固定。这些连接是双向的。竞争对手最初提供 $$$m$$$ 连接。您的竞争对手提供的第 $$$i$$$ 连接将连接节点 $$$fa_i$$$ 和 $$$fb_i$$$,成本为 $$$fw_i$$$。

您有一个想要提供的 $$$k$$$ 联系人列表。保证这组连接不形成任何环路。这些连接中的第 $$$j$$$ 将连接节点 $$$ga_j$$$ 和 $$$gb_j$$$。这些连接也是双向的。这些连接的成本尚未确定。

您可以将这些连接的价格设置为任意整数值。这些价格是针对每个连接独立设置的。设置价格后,客户将选择 $$$n - 1$$$ 连接,使所有节点都连接在单个网络中,并且所选连接的总成本尽可能最小。如果有多种方式选择此类网络,客户将选择任意一种,同时最大限度地提高其中的连接数量。

您希望以这样的方式设置价格,以便客户选择所有 $$$k$$$ 连接,并且使连接的价格总和最大化。

打印您可以实现的最大利润,如果没有限制,则打印 $$$-1$$$。

输入

输入的第一行将包含三个整数 $$$n$$$、$$$k$$$ 和 $$$m$$$ ($$$1 \leq n, k, m \leq 5 \cdot 10^5, k \leq n-1$$$),分别是节点数、你的连接数和竞争对手的连接数。

接下来的 $$$k$$$ 行包含两个整数 $$$ga_i$$$ 和 $$$gb_i$$$ ($$$1 \leq ga_i, gb_i \leq n$$$, $$$ga_i \not= gb_i$$$),代表节点 $$$ga_i$$$ 和 $$$gb_i$$$ 之间的连接之一。您的连接集保证是非循环的。

接下来的 $$$m$$$ 行每行包含三个整数,$$$fa_i$$$、$$$fb_i$$$ 和 $$$fw_i$$$ ($$$1 \leq fa_i, fb_i \leq n$$$, $$$fa_i \not= fb_i$$$, $$$1 \leq fw_i \leq 10^9$$$),表示节点 $$$fa_i$$$ 和 $$$fb_i$$$ 之间的竞争对手的连接之一,成本为 $$$fw_i$$$。这些连接中没有一个将节点与其自身连接,并且这些连接中没有一对连接同一对节点。此外,这些连接是按成本非递减顺序给出的(即,对于所有有效的 $$$i$$$,$$$fw_{i-1} \leq fw_i$$$)。

请注意,某些连接可能同时出现在您的集合和竞争对手的集合中(尽管任何连接都不会在其中一个集合中出现两次)。

保证您的所有连接和竞争对手的连接联合形成一个连接的网络。

输出

打印一个整数,如果您适当地设置连接价格,您可以获得的最大可能利润。如果利润无界,则打印$$$-1$$$。

示例

输入 #1

4 3 6
1 2
3 4
1 3
2 3 3
3 1 4
1 2 4
4 2 8
4 3 8
4 1 10

输出 #1

14

输入 #2

3 2 1
1 2
2 3
1 2 30

输出 #2

-1

输入 #3

4 3 3
1 2
1 3
1 4
4 1 1000000000
4 2 1000000000
4 3 1000000000

输出 #3

3000000000

注意

在第一个示例中,最佳连接 $$$1-3$$$ 成本 $$$3$$$,连接 $$$1-2$$$ 成本 $$$3$$$,连接 $$$3-4$$$ 成本 $$$8$$$。在这种情况下,最便宜的连接网络的成本为 $$$14$$$,客户将选择一个可以选择您所有连接的网络。

在第二个示例中,只要您的第一个连接成本为 $$$30$$$ 或更少,无论第二个连接的成本是多少,客户都会选择您的两个连接,因此在这种情况下您可以获得无限的利润。