Minimum Spanning Tree (Kruskal)
mediumGraphs II+20 XPTime limit 2s
A state wants to connect n villages with fibre cable. Laying cable on a possible route u v w costs w lakh rupees. Choose routes so that every village is connected (directly or through others) at the minimum total cost.
Input:
- line 1:
n m - next
mlines: a possible routeu v w(two-way)
Output: the minimum total cost, or -1 if it is impossible to connect all villages.
Constraints: 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 3·10⁴, 1 ≤ w ≤ 10⁵, u ≠ v; several routes may join the same pair. The answer fits in a 32-bit signed integer.
Think about it: Kruskal's algorithm: sort routes by cost and take each one that joins two different components (check with Union-Find); skip routes that would make a cycle. You need exactly n − 1 routes. O(m log m). Prim's algorithm with a min-heap works too.
Sample input 1
4 5 1 2 1 2 3 4 1 3 3 3 4 2 2 4 5
Sample output 1
6
Sample input 2
3 1 1 2 7
Sample output 2
-1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).