ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1982. Electrification Plan

This is not an MST problem.
Posted by grinrag 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
Re: This is not an MST problem.
Posted by Ritesh Rastogi 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
Re: This is not an MST problem.
Posted by D4nick 16 Oct 2020 02:49
Yeah, not MST, it's MSF :) :) :)