| ENG RUS | Timus Online Judge |
Обсуждение задачи 1982. План электрификацииSmilodon_am [Obninsk INPE] If you have WA #9 [6] // Задача 1982. План электрификации 6 ноя 2013 11:26 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. Arseniy Re: If you have WA #9 [4] // Задача 1982. План электрификации 7 фев 2014 22:48 HM, i have right output on this test, but WA 9 SquidBoy Re: If you have WA #9 [3] // Задача 1982. План электрификации 21 сен 2015 04:38 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.... Arseniy писал(a) 7 февраля 2014 22:48 HM, i have right output on this test, but WA 9 lrdx Re: If you have WA #9 // Задача 1982. План электрификации 27 окт 2015 20:10 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 Booster Re: If you have WA #9 [1] // Задача 1982. План электрификации 19 фев 2019 12:07 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 Hristo Nikolaev (B&W) Re: If you have WA #9 // Задача 1982. План электрификации 27 мар 2023 17:15 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 bosenok Re: If you have WA #9 // Задача 1982. План электрификации 19 июн 2014 04:17 c[i][j] = c[j][i] This is wrong test Kirill~ WA2 // Задача 1982. План электрификации 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 D4nick Interesting problem, I like it, thanks // Задача 1982. План электрификации 16 окт 2020 02:58 grinrag This is not an MST problem. [2] // Задача 1982. План электрификации 8 окт 2019 22:49 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 Ritesh Rastogi Re: This is not an MST problem. // Задача 1982. План электрификации 3 мар 2020 06:16 This is indeed an MST problem ; with the idea of a dummy vertex brought it. More about this problem can be read in the editorial of this problem - https://codeforces.com/problemset/problem/1245/D D4nick Re: This is not an MST problem. // Задача 1982. План электрификации 16 окт 2020 02:49 Yeah, not MST, it's MSF :) :) :) amomorning easy MST [1] // Задача 1982. План электрификации 23 май 2015 07:37 use prim or kruskal can solve it. buyolitsez Re: easy MST // Задача 1982. План электрификации 17 мар 2019 10:42 Thank you Sherxon WA2? [1] // Задача 1982. План электрификации 26 ноя 2016 03:19 Can anybody please give me cases for Test2 ? Manole Victor Re: WA2? // Задача 1982. План электрификации 12 фев 2019 17:57 If you only go through the matrix and saved the minimum value, it is not the solution for that problem. Amil Khare Explanation of the problem Statement & Hint needed [9] // Задача 1982. План электрификации 21 сен 2017 06:21 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 Mahilewets Nikita [BSUIR] Re: Explanation of the problem Statement [1] // Задача 1982. План электрификации 21 сен 2017 09:25 Questions you are asking are not about the statement Questions you are asking are about the solution Amil Khare Re: Explanation of the problem Statement // Задача 1982. План электрификации 21 сен 2017 09:27 Oh sorry, my bad! However can you please help me ? I will change the topic of the comment. Mahilewets Nikita [BSUIR] Re: Explanation of the problem Statement [6] // Задача 1982. План электрификации 21 сен 2017 09:27 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..." Mahilewets Nikita [BSUIR] Re: Explanation of the problem Statement [1] // Задача 1982. План электрификации 21 сен 2017 09:28 So we need to connect the other n-k cities Amil Khare Re: Explanation of the problem Statement // Задача 1982. План электрификации 21 сен 2017 09:29 Oh, got it ! Thanks a lot :) Mahilewets Nikita [BSUIR] Re: Explanation of the problem Statement [3] // Задача 1982. План электрификации 21 сен 2017 09:29 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 Amil Khare Re: Explanation of the problem Statement [2] // Задача 1982. План электрификации 21 сен 2017 09:30 No information about Graphs, you mean that whether it's directed or undirected? Mahilewets Nikita [BSUIR] Re: Explanation of the problem Statement [1] // Задача 1982. План электрификации 22 сен 2017 09:00 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 Amil Khare Re: Explanation of the problem Statement // Задача 1982. План электрификации 27 сен 2017 17:26 Thanks a lot for helping me ! :) Nithin What is my code doing? [1] // Задача 1982. План электрификации 16 май 2017 22:38 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 Mahilewets Re: What is my code doing? // Задача 1982. План электрификации 17 май 2017 20:12 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. shweta prims algo using priority queue [1] // Задача 1982. План электрификации 24 июн 2016 16:09 in prims algo implementation using priority queue, how can i decrease a key in priority queue ? rihaz zahir Re: prims algo using priority queue // Задача 1982. План электрификации 24 авг 2016 11:36 you can't change the element. you have to make your own min-heap for the dijkistra gh0st WA#28 // Задача 1982. План электрификации 8 сен 2015 01:20 Can anybody give some hits or information on test 28, thanks! Adhambek prim's algorithm // Задача 1982. План электрификации 10 янв 2015 17:19
|