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.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 18:57:17 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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
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?
Your solution fails on this test:
4 5
1 3 1
2 3 2
2 4 1
4 3 1
1 4 1
Please explain how to find the maximal weighted edge in the cycle formed by adding the new edge.
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.
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
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.
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))
I didn't understand. How do you search for mst?
I already got a AC so that you can just see the code) https://pastebin.com/J3XWnPCP
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?
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)
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).
Indeed, the α(n) = O(log (n)) (and α(n) = O(n!) :) ). But for any n not exceeding 10^600, α(n) < 5
So, we could consider your algorithm as O(E*V) in time for practical purposes?
I think yes
as I know, usually this is written as O(V*E*α), meaning V*E*const
about your solution: on the test "2 2 1 1 1 2 2 2" it displays "0, -1", is this normal?
By the statement of the problem, I think this case is impossible. Anyway, my initial approach is too inefficient and I already discarded it.
it seemed to me that your solution works for O(VE), is not it?