Hello CF! How do I calculate 2nd best MST? Is removing the shortest edge in the 1st MST from the original graph and calculating MST again would be enough? Also, how do I calculate n'th best MST in general?

Before contest

Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

25:40:12

Register now »

Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

25:40:12

Register now »

*has extra registration

Before contest

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

25:40:12

Register now »

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

25:40:12

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3556 |

2 | wxhtxdy | 3520 |

3 | Radewoosh | 3409 |

4 | Benq | 3368 |

5 | mnbvmar | 3280 |

6 | ecnerwala | 3278 |

7 | LHiC | 3276 |

8 | sunset | 3264 |

9 | maroonrk | 3159 |

10 | TLE | 3145 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 189 |

2 | Radewoosh | 177 |

3 | tourist | 173 |

4 | antontrygubO_o | 172 |

5 | Vovuh | 167 |

6 | PikMike | 166 |

7 | rng_58 | 157 |

8 | majk | 156 |

9 | farmersrice | 153 |

9 | Um_nik | 153 |

Hello CF! How do I calculate 2nd best MST? Is removing the shortest edge in the 1st MST from the original graph and calculating MST again would be enough? Also, how do I calculate n'th best MST in general?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2019 12:24:48 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

First, build MST using for example Kruskal's algorithm. Next, we go through the edges that are not included in MST, and try to add them. When we add an edge, a loop appears in the tree. We need to find the maximum edge in this cycle, this is done in log, using a binary lifting, and delete this edge, recount mincost, update the answer, and put deleted edge back. ̶T̶o̶ ̶f̶i̶n̶d̶ ̶n̶’̶t̶h̶ ̶b̶e̶s̶t̶ ̶M̶S̶T̶ ̶w̶e̶ ̶c̶a̶n̶ ̶a̶d̶d̶ ̶a̶l̶l̶ ̶c̶o̶s̶t̶s̶ ̶i̶n̶ ̶v̶e̶c̶t̶o̶r̶,̶ ̶s̶o̶r̶t̶ ̶t̶h̶e̶m̶ ̶a̶n̶d̶ ̶t̶a̶k̶e̶ ̶n̶’̶t̶h̶.̶

Can you elaborate on how to find the maximum edge on the tree using binary lifting?

Also, what do you mean by "add all costs in vector, sort them and take n’th."?

After we built the MST, we got a tree. And for this tree we will make a pre-calculation. We make up[i][j] — j'th parent of vertex i, and also mx[i][j] is the maximum edge from vertex i to j-th parent. When we want to try adding some edge (u-v) to the tree, we get a cycle u -> lca (u, v) -> v -> u. That is, the maximum edge on path = max (max edge on path u -> lca (u, v) , v -> lca (u, v)). This is easy to do. You can read about binary lifting here:Binary lifting. But now I'm not sure if this works to find n-th MST. For first n−1 MSTs — it's correct.

Dfs look like this:

For 2nd MST it is enough to change exactly one edge from initial MST (but it doesn't have to be smallest one). Solution is similar as first comment : iterate over new added edge and erase second biggest from the cycle (biggest one is now added, otherwise we had wrong MST construction).

Even for 3rd MST things are much complicated — sometimes answer is again changing just one edge from initial MST, but sometimes it is optimal to change two edges (one more from second MST, not initial one).

Currently for me it looks like, $$$n$$$-th MST will have exactly one different edge than at least one of first $$$n-1$$$ MSTs. In case that is correct, whole process can be done in $$$O$$$($$$n^2 \cdot (E + V) $$$ $$$log$$$ $$$V$$$) — you can check did you count some MST in first $$$n-1$$$ with hashing. But I am not sure in correctness.

thank you!

Wikipedia says that the kth MST problem is NP-Hard but can be approximated.

I saw that problem about MST with exactly $$$k$$$ vertices is NP hard (as you need to check all subsets of size $$$k$$$). I think I found some papers about $$$k$$$-th spanning tree with solutios in polynomial time. But I didn't read them :)

You can share Wiki page.

There is actually a video tutorial by Algorithms Live about this problem.