Robin's blog

need help calculating n'th best MST
By Robin, history, 5 years ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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̶.̶

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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."?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Dfs look like this:

        void dfs(int v, int p)
{
    tin[v]=++timer;
    up[v][0]=p;
    int mxx=0;
    for(auto u : graph[v]) if(u.F==p) mxx=u.S;
    mx[v][0]=mxx;
    for(int i=1;i<=lg;i++){
        up[v][i]=up[up[v][i-1]][i-1];
        mx[v][i]=max(mx[v][i-1],mx[up[v][i-1]][i-1]);
    }
    for(auto u : graph[v]) if(u.F!=p) dfs(u.F,v);
    tout[v]=++timer;
}
        → Reply
»
5 years ago, # |
← Rev. 7   Vote: I like it +7 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
11 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I saw a problem in Luogu to calculate n'th best MST. I don't know the specific solution, but you can find the problem here: problem link.

→ Reply