Does anyone know how to prove the math solution for I would walk 500 miles?

solution link: https://usaco.guide/solutions/usaco-946#solution-3.

The two lowest-weight edges of the MST are (N-1,N) and (N-2,N). Can you figure it out from there?

2 Likes

Hi, would you mind explaining a bit further? Can’t quite wrap my mind around it.

What other edges are part of the MST? (If you don’t know, perhaps write a program to print them out.)

Hi, I have since written up a full editorial for the \mathcal{O}(1) solution: https://usaco.guide/solutions/usaco-946

Hope it can be of some use!