Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
If you have WA #9 | Smilodon_am [Obninsk INPE] | 1982. План электрификации | 27 мар 2023 17:15 | 7 |
First I used Kruskal algo but got WA9 verdict. My program didn't give right answer for next test: 4 1 4 0 1 1 100000 1 0 1 100000 1 1 0 100000 100000 100000 100000 0 right answer: 100002 Implementation of Prim algo gave the correct answer at last. HM, i have right output on this test, but WA 9 This test helped me.... 5 2 1 3 0 1 2 3 4 1 0 2 3 4 2 2 0 3 4 3 3 3 0 4 4 4 4 4 0 =8 (I was getting 9). Basically my algorithm (roughly Prim's) tried to short-cut checking vertex weights. For any node, make sure you check verices to ALL nodes.... HM, i have right output on this test, but WA 9 Some tests: 4 2 1 4 0 4 8 9 4 0 2 7 8 2 0 1 9 7 1 0 Answer 3 4 2 1 3 0 6 7 8 6 0 2 3 7 2 0 4 8 3 4 0 Answer 5 Edited by author 27.10.2015 20:10 5 3 1 3 2 0 1 2 3 4 1 0 2 3 4 2 2 0 3 4 3 3 3 0 4 4 4 4 4 0 answer is 7 Edited by author 19.02.2019 12:09 One more test that helped me to find my error for WA #9. 5 2 1 5 0 1 100 150 200 1 0 10 50 200 100 10 0 11 100 150 50 11 0 2 200 200 100 2 0 Answer: 13 c[i][j] = c[j][i] This is wrong test |
WA2 | Kirill~ | 1982. План электрификации | 23 мар 2022 22:37 | 1 |
WA2 Kirill~ 23 мар 2022 22:37 Check this: if (!used[j] and min_e[j] < min_e[v] and j!=v) { Edited by author 23.03.2022 22:57 |
Interesting problem, I like it, thanks | D4nick | 1982. План электрификации | 16 окт 2020 02:58 | 1 |
|
This is not an MST problem. | grinrag | 1982. План электрификации | 16 окт 2020 02:49 | 3 |
This is not an MST problem, because finally, we can have a graph with several connected components (not a tree). For example, if a city has a power station and the price to build a line to another city is too high we can just isolate this city. Such test: 4 2 1 4 0 1 1 7 1 0 5 2 1 5 0 2 7 2 2 0 The answer is 2. We build line 1 <-> 2, 1 <-> 3. The total price is 2. It's not necessary to build any line to city 4. I don't know, maybe there are no tests for such cases. Edited by author 09.10.2019 16:52 Yeah, not MST, it's MSF :) :) :) |
easy MST | amomorning | 1982. План электрификации | 17 мар 2019 10:42 | 2 |
use prim or kruskal can solve it. |
WA2? | Sherxon | 1982. План электрификации | 12 фев 2019 17:57 | 2 |
WA2? Sherxon 26 ноя 2016 03:19 Can anybody please give me cases for Test2 ? Re: WA2? Manole Victor 12 фев 2019 17:57 If you only go through the matrix and saved the minimum value, it is not the solution for that problem. |
Explanation of the problem Statement & Hint needed | Amil Khare | 1982. План электрификации | 27 сен 2017 17:26 | 10 |
Hello, I didn't understand the problem statement correctly. Do cities having power stations need to be connected to each other? The solution can be also having more than 1 connected components( Graphs ), right? Edited by author 21.09.2017 09:28 Edited by author 21.09.2017 09:32 Questions you are asking are not about the statement Questions you are asking are about the solution Oh sorry, my bad! However can you please help me ? I will change the topic of the comment. The first question is maybe OK. It is about the statement. So there is "k cities have stations, the other cities need to be connected..." So we need to connect the other n-k cities Oh, got it ! Thanks a lot :) And second question is really about the solution To understand it pay your attention to fact That there is NO INFORMATION ABOUT ANY GRAPHS in the statement No information about Graphs, you mean that whether it's directed or undirected? Statement doesn't contain the word "graph" So the graph is just a mathematical model used for solving such kind of problems not something from statement Also remember that it is ACM ICPC tradition to write informal statements Statements which need to be formalized Thanks a lot for helping me ! :) |
What is my code doing? | Nithin | 1982. План электрификации | 17 май 2017 20:12 | 2 |
I have implemented a greedy algorithm to solve this problem and it got accepted and after reading the discussion I have noticed that many people used Prims algorithm to solve. I have no idea of what Prims algorithm is. Could anyone please tell me what exactly is my code doing and how is it different from Prims algorithm? [code deleted] Edited by moderator 21.01.2020 16:06 There are only three algorithms for finding minimal spanning. Their complexities are different, but idea is the same. So, we can say that they all are actually the same algorithm. Your code is most similar to Kruskal's algo. You arr finding the smallest edge and adding it to MST. |
prims algo using priority queue | shweta | 1982. План электрификации | 24 авг 2016 11:36 | 2 |
in prims algo implementation using priority queue, how can i decrease a key in priority queue ? you can't change the element. you have to make your own min-heap for the dijkistra |
WA#28 | gh0st | 1982. План электрификации | 8 сен 2015 01:20 | 1 |
WA#28 gh0st 8 сен 2015 01:20 Can anybody give some hits or information on test 28, thanks! |
prim's algorithm | Adhambek | 1982. План электрификации | 10 янв 2015 17:19 | 1 |
|