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

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

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.

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

How to find 2nd Minimal Spanning Tree? At first, let's build MST. Consider all edges that doesn't belong to MST. We can try to add them independently to MST. YEA, we've got a cycle. We can erase any edge in a cycle and rest edges will be Spanning Tree. Obviously, it's good idea to erase edge with maximal weight (and this edge mustn't be our added edge, off course:) ). Then relax our answer.

Code: https://pastebin.com/TraXQSY0

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

    Thank you very much, I got your approach!

    But I still would appreciate knowing why my initial approach doesn't work. Could someone provide some test case where it fails, please?

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

    Please explain how to find the maximal weighted edge in the cycle formed by adding the new edge.

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

      In this problem N <= 500, so you can do it in a stupid way.

      For example, you add edge (u, v). Find lca(u, v) and consider all edges on the way from u to lca and from v to lca. take maximal.

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

By the way, there is, perhaps a simpler solution: find a mst, then for each edge from the mst to find a mst in the graph without it, the answer is the minimum of the resulting mst.

upd: I did not quite understand the constraints in the problem, so maybe this solution is too slow

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

    I think it would be O(E²*logV). The problem didn't give the constraint to the total of edges but in the comments at the forum of the online judge someone argued that he tested and found out that the edges can be 250000 in a test case. So, it probably wouldn't pass.

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

      but note in the mst only O(V) edges, and you can search for mst O(E * α(E, V)), so it will be O(V * E * α(E, V))

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

        I didn't understand. How do you search for mst?

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

          I already got a AC so that you can just see the code) https://pastebin.com/J3XWnPCP

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

            If I understood, you ran Kruskal one time for the total graph to get ans1 and after, for each edge that was in the MST, you ran Kruskal for the total graph without it and took the minimum of the total costs to get ans2. So it would be O(E*V*logV). Is it correct?

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

              everything is correct, except the complexity of the algorithm) Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in O(E*α(V)) time , where α is the extremely slowly growing inverse of the single-valued Ackermann function. (it's from wiki) p.s (we can assume that α(V) is always < 5)

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

                By the page 452 of Cormen's book second edition, the complexity is O(E*α(V)) in time if you consider that the disjoint-set data structure utilizes the heuristic of union by rank and path compression (which you are already using) and that |E| >= |V| — 1 (which is true by the statement of the problem). In the same part of the book, the author says that α(|V|) = O(logE) and concludes that the total time execution for Kruskal algorithm is O(E*logE). If we consider in addition that |E| < |V|² (which isn't the case in this problem), than log(|E|) = O(logV) and we can redefine the time of execution to O(E*logV). So, I think the complexity of your algorithm would be O(E*V*logE).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

about your solution: on the test "2 2 1 1 1 2 2 2" it displays "0, -1", is this normal?

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

    By the statement of the problem, I think this case is impossible. Anyway, my initial approach is too inefficient and I already discarded it.