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.
solution link: https://blog.csdn.net/u012596172/article/details/42610761
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.
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.
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.
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
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.
I suppose, without having a proof, that you're wrong.
proof by AC. xD haha, no. Well, It was the first thing that seemed reasonable that passed the testcases.
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.
Actual solution:
Sort the edges. Do a bruteforce like this:
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.