|
|
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 Check this: if (!used[j] and min_e[j] < min_e[v] and j!=v) { Edited by author 23.03.2022 22:57 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 :) :) :) use prim or kruskal can solve it. Can anybody please give me cases for Test2 ? If you only go through the matrix and saved the minimum value, it is not the solution for that problem. 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 ! :) 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. 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 Can anybody give some hits or information on test 28, thanks! |
|
|