stefanbalaz2's blog

Weird MST related problem solution(at least for me)
By stefanbalaz2, history, 4 years ago, In English

I came across a problem(link in the bottom), brief description:

Given n nodes (n<=10) and m edges (m<=25), whose weights are wi(wi<=1000), u should construct 2 spanning trees from those edges such that the sum of the weights of the chosen edges is minimal.

Then i came across a solution(link in the bottom), brief description:

Lets define important edges. Important edge is an edge such that it is included in every MST. After finding important edges for our graph, we know that they will definatelly be in either first spanning tree or the second spanning tree, so we will try all possibilities of assigning important edges to those two spanning trees, and when trying a possible assignment of important edges, we will first add them to the corresponding spanning tree we assigned them to, and then we will simulate a regular MST building process for the remaining edges, first to build up the first spanning tree, then the second spanning tree. Minimum taken from all the possibilities is the answer.

I have spent hours on trying to prove this, yet i made no progress. Maybe the solution isnt actually correct but rather just passed the test cases.

I would be grateful if someone would have a look at this problem solution.

problem link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=1748&mosmsg=Submission+received+with+ID+25718261

solution link: https://blog.csdn.net/u012596172/article/details/42610761

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

consider any spanning tree, I can affirm that some of the edges will be in the final result, otherwise I can exchange one of the spanning trees in the answer for this one, therefore we can consider all the subsets of any spanning tree and try each one. Clearly it also works for the interception of all spanning trees.

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

    That's ok but why should trying the other edges greedily work? For me it feels like it shouldn't. You can solve this problem in reasonable complexity with weighted matroid union.

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

      I think that the remaining edges that are in an optimal case can be painted in two colors, then it seems to me that the edges that should be in 2 and are in 1 join the same sets of node components and can be transferred by the exchange argument. Yes, this problem can also be solved by matroid methods.

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

        If thats the case, i suppose that after picking a partition of edges(by partition i mean an unordered partition, like 11000 and 00111 are the same) , u can always choose to greedily first build the 1st tree then the 2nd tree, but unfortunately, that gives WA

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

          It seems to me that it is difficult to prove, that through an exchange argument we can pass edges from one mst to the other optimizing one of them, I suppose, without having a prove, that these exchanges have an optimal distribution with the necessary edges in all spanning tree.

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

            I suppose, without having a proof, that you're wrong.

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

              proof by AC. xD haha, no. Well, It was the first thing that seemed reasonable that passed the testcases.

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

                Yesterday I hacked the solution to a problem from 2019 Brazilian Subregionals by a rookie in my university, TL is like 0.5s and my test makes his solution run for almost 1 minute. Sometimes tests are shit.

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

Actual solution:

Sort the edges. Do a bruteforce like this:

bf():
  if we have 2 spanning trees, make ans = min(ans, cost of 2 spanning trees)
  otherwise, take the edge with min cost not chosen that can be put into one of the 2 subgraphs without creating a cycle. If there's no such edge, return. Else, if our current 2 subgraphs are indeed part of the answer it's clear that this edge appears in the answer (by exchange argument) so we try putting it into the 2 colors by bruteforce

The complexity of this is O(2^(2*N-2)*N) because we have a decision tree of depth (2*N-2) with branching factor 2 and we can handle the connected components by a linear pass through the edges.

→ Reply