Вы руководите мобильным оператором и хотите предлагать конкурентоспособные цены для создания сети.
В сети есть $$$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$$$. Среди этих подключений нет таких, которые соединяют узел сам с собой, а также нескольких подключений между одной и той же парой узлов. Кроме того, эти подключения заданы в порядке возрастания цены (то есть $$$fw_{i-1} \leq fw_i$$$ для всех $$$i$$$).
Обратите внимание, некоторые подключения могут присутствовать как в вашем списке, так и в списке конкурента (но ни одно не будет присутствовать дважды в одном списке).
Гарантируется, что объединение ваших подключений и подключений конкурента связывает все узлы.
Выведите единственное число — максимально возможную прибыль, если вы можете произвольно выбирать стоимости ваших подключений. Если прибыль неограничена, выведите $$$-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
14
3 2 1
1 2
2 3
1 2 30
-1
4 3 3
1 2
1 3
1 4
4 1 1000000000
4 2 1000000000
4 3 1000000000
3000000000
В первом примере оптимально дать стоимость $$$3$$$ подключению $$$1-3$$$, стоимость $$$3$$$ подключению $$$1-2$$$, стоимость $$$8$$$ подключению $$$3-4$$$. В таком случае самый дешевый способ получить связную сеть стоит $$$14$$$, и клиент из таких способов выберет тот, которые содержит все ваши подключения.
Во втором примере до тех пор, пока ваше первое подключение стоит $$$30$$$ или меньше, клиент будет вынужден выбрать оба ваших подключения независимо от цены второго, и вы можете получить неограниченную прибыль.
Название |
---|