Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Graph problem

Revision en1, by noobinho, 2018-07-19 20:31:25

I'm trying to do this problem: http://acm.timus.ru/problem.aspx?space=1&num=1416. It consists in a simple, undirected and weighted graph for which is demanded to calculate the second minimum total cost: a cost of a configuration (different than the minimum-spanning-tree) which connects all vertex and has the smallest cost not less than the cost given by the minimum-spanning-tree. If there isn't such a configuration it's demanded to indicate that. I did the following code: https://ideone.com/e.js/y4CcBz. It generates the minimum-spanning-tree with Kruskal and tries to eliminate the edges of this tree one by one from the bigger to the smallest. For each edge eliminated, it tries to connect the edges that weren't in the minimum-spanning-tree, one by one, from the bigger to the smallest, and verifies with a DFS if the resulting graph has only one connected component. If so, it stops. Else, it reconnects the edge of the minimum-spanning-tree and goes to the next iteration. Since my approach gives wrong answer, I want to know what is wrong with it and what is the correct approach. Thanks in advance.


  Rev. Lang. By When Δ Comment
en1 English noobinho 2018-07-19 20:31:25 1128 Initial revision (published)