Discussion @ 1982. Electrification Plan @ Timus Online Judge

grinrag This is not an MST problem. [2] // Problem 1982. Electrification Plan 8 Oct 2019 22:49

This is not an MST problem, because finally, we can have a graph with several connected components (not a tree). For example, if a city has a power station and the price to build a line to another city is too high we can just isolate this city. Such test:
4 2
1 4
0 1 1 7
1 0 5 2
1 5 0 2
7 2 2 0

The answer is 2.
We build line 1 <-> 2, 1 <-> 3. The total price is 2. It's not necessary to build any line to city 4.

I don't know, maybe there are no tests for such cases.

Edited by author 09.10.2019 16:52

Ritesh Rastogi Re: This is not an MST problem. // Problem 1982. Electrification Plan 3 Mar 2020 06:16

This is indeed an MST problem ; with the idea of a dummy vertex brought it. More about this problem can be read in the editorial of this problem - https://codeforces.com/problemset/problem/1245/D

D4nick Re: This is not an MST problem. // Problem 1982. Electrification Plan 16 Oct 2020 02:49

Yeah, not MST, it's MSF :) :) :)

Discussion of Problem 1982. Electrification Plan