Weird MST related problem solution(at least for me)

Правка en1, от stefanbalaz2, 2020-11-12 21:51:27

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

Теги mst, trees

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский stefanbalaz2 2020-11-12 21:51:27 1548 Initial revision (published)