http://www.usaco.org/index.php?page=viewproblem2&cpid=1138
I’m having some trouble understanding the official editorial. I get we’re looking for an MST here, but how come we’ve only got 2N nodes instead of 4N? Problem statement says there are 4N distinct locations to connect.
And since permuting some portals “erases” the edges to other portals, how can we just greedily grab all the edges?
There’s definitely some simple reduction I’m missing here. Any help is appreciated.