Discussion @ 1160. Network @ Timus Online Judge

MST ?

Posted by Roman Lipovsky 13 Oct 2004 00:04

I think, that 1160 is MST problem. Is my idea correct?
And explain me, please, is my output for sample input correct :
1
3
1 2
2 3
3 4

Re: MST ?

Posted by dimozzz 18 Jan 2007 21:30

No, I's not MST. Read problem again.

Re: MST ?

Posted by GaLL [fac. of philology Tyumen SU] 18 Jan 2007 22:42

It's MST, but with another metric.

Re: MST ?

Posted by SkorKNURE 23 Sep 2008 23:30

It's classic MST: all MST with minimum total weight are also ones with minimal weight of the maximal rib. Simple nonmodified Cruscal solve it by ~0.15 sec.

Discussion of Problem 1160. Network