1750. The Cheapest Plan With Links Already Built

An UNDIRECTED graph has n vertices and m edges, edge i joining u and v at cost w. Some edges are MANDATORY, marked by a flag f of 1; the rest have f equal to 0.

Print the smallest total cost of a plan that uses every mandatory edge, where a plan keeps every pair of vertices joined that was joined before and uses no more edges than necessary. Print -1 when no plan can contain all the mandatory edges.

4 vertices, 1-2 (1) must, 2-3 (2), 3-4 (3), 1-4 (9) -> 6 4 vertices, 1-2 (1), 2-3 (2), 3-4 (3), 1-4 (9) must -> 12 3 vertices, 1-2 (1) must, 2-3 (2) must, 1-3 (1) must -> -1 1 vertex, 1-1 (5) must -> -1 3 vertices, 1-2 (1), 2-3 (2) -> 3

The second example forces the dear edge in, so the plan is 1-4, 1-2, 2-3 and costs 12 instead of 6. The third forces all three edges of a triangle, which is not a plan at all because it holds a cycle. The fourth forces a self-loop, which no plan ever contains.

## When the answer is -1

Exactly when the mandatory edges contain a CYCLE, counting a self-loop as a cycle of length one. A plan is acyclic by definition, so it can never contain one; and if the mandatory edges are acyclic then they are part of some plan, because any acyclic set of edges extends to a spanning forest.

That last claim is worth being sure of. Take the mandatory edges, merge their endpoints into groups, and keep adding any edge joining two different groups until none is left. The result is acyclic, contains the mandatory edges, and spans every piece, since any two vertices joined in the graph end up in the same group once no joining edge remains.

## The three things that have to be said

directed? no. self-loops? allowed, and a mandatory self-loop forces -1 immediately. parallel edges? allowed, and two mandatory copies of one pair also force -1, since the pair of them is a cycle of length two. disconnected? allowed, and a plan is a spanning forest.

## What most people try first

Running Kruskal normally and then checking that the mandatory edges came out. They usually do not, and there is no repair: on the second example Kruskal takes the three cheap edges and the mandatory one is not among them.

The second attempt is to give the mandatory edges a cost of zero and run Kruskal. That gets the right EDGE SET and the wrong total, and remembering to add their real costs back turns it into the method below with an extra step.

## Take the mandatory edges first, then Kruskal on the rest

put every vertex in its own group for each mandatory edge, in input order: if its two ends are already in one group: print -1 and stop merge them and add its cost to the total then sort the remaining edges by cost and run the usual loop: take an edge when its two ends are in different groups

## Why starting with the mandatory edges is correct

Think of the mandatory edges as already built, which merges their endpoints into super-vertices. Any plan containing them is exactly a plan of the graph with those merges applied, plus the mandatory edges themselves. Their total cost is a constant, so minimising the whole is minimising the rest, and the rest is an ordinary cheapest-plan problem on the merged graph. Kruskal solves that, and the cut property applies unchanged with groups in place of vertices.

Note that the mandatory edges do NOT need sorting, and that processing them in input order is enough: a cycle among them is detected whichever order they are merged in, because whether a set of edges is acyclic does not depend on the order it is examined.

## Watch the size of the total

A plan holds up to n - 1 edges at 10^9 each, so the total reaches about 2 * 10^14. A signed 32-bit integer stops at 2147483647, so the accumulator must be 64-bit, even though each individual cost fits in 32.

## Cost

Time O(m log m) for the sort plus near-constant time per group operation. Space O(n + m). No recursion.

## Related

Problem 1741 is the version with no mandatory edges. Problem 1752 asks which edges are mandatory whether you like it or not, in the sense that every cheapest plan uses them. Problem 1746 asks what the next cheapest total is, which is the same shape of question answered by forcing one edge OUT rather than in.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000` - `f` is 0 or 1 - `u` may equal `v`, so self-loops can occur, and the same pair may be listed more than once - the graph may be disconnected