Блог пользователя themechanicalcoder

Need help in a problem

Автор themechanicalcoder, история, 5 лет назад, По-английски

I was solving the problem Uva 10600 in which we have to find the minimum and second minimum spanning tree I found the minimum spanning tree using kruskal's algorithm and stored the edges in a vector mst then to find the second minimum spanning tree I did this

second_tot_wt=INF for edge in mst : second_tot_wt=min(second_tot_wt,total weight of the minimum spanning tree ignoring this edge)

my code was fine on the test case but I am getting the verdict wrong answer can someone please help

my solution

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

Hi! When you try to find the second spanning tree you need to check that after ignoring some edge, every node is in the same component, for example:

  • 4 nodes and 4 edges
  • from 1 to 2 weight 1
  • from 2 to 3 weight 1
  • from 1 to 3 weight 3
  • from 3 to 4 weight 1

when you run kruskal you found that the mst uses edges 1, 2, and 4, then you try to remove each edge in the mst, but if you remove edge 4 you get an answer equal to 2 and it is wrong, because you don't connect node 4 with nodes 1, 2, and 3.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I understood what you are trying to say but how will I implement that

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      After you run kruskal, iterate over each node and check that the parent is equal for every node, something like that:

      int cur = kruskal(mst[i]);
bool is_valid = true;
for( int i = 0; i < n; ++i ) {
  if( find_(i) != find_(0) ) {
    is_valid = false;
    break;
  }
}
if( is_valid ) {
  swt=min(swt, cur);
}
      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        What if is_valid is false what will be the answer in that case ?

        → Ответить
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          When is_valid is equal to false means that after removing edge mst[i] doesn't exist a valid mst. So, the only way to get false in every iteration is when the original graph is a tree, because you don't have extra edges. I didn't read the statement, so you should check what happens if the original graph is a tree, or even if the original graph doesn't connect every node in the same component

          → Ответить