| Show all threads Hide all threads Show all messages Hide all messages |
| If you have WA #9 | Smilodon_am [Obninsk INPE] | 1982. Electrification Plan | 27 Mar 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. Electrification Plan | 23 Mar 2022 22:37 | 1 |
WA2 Kirill~ 23 Mar 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. Electrification Plan | 16 Oct 2020 02:58 | 1 |
|
| This is not an MST problem. | grinrag | 1982. Electrification Plan | 16 Oct 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. Electrification Plan | 17 Mar 2019 10:42 | 2 |
use prim or kruskal can solve it. |
| WA2? | Sherxon | 1982. Electrification Plan | 12 Feb 2019 17:57 | 2 |
WA2? Sherxon 26 Nov 2016 03:19 Can anybody please give me cases for Test2 ? Re: WA2? Manole Victor 12 Feb 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. Electrification Plan | 27 Sep 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. Electrification Plan | 17 May 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. Electrification Plan | 24 Aug 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. Electrification Plan | 8 Sep 2015 01:20 | 1 |
WA#28 gh0st 8 Sep 2015 01:20 Can anybody give some hits or information on test 28, thanks! |
| prim's algorithm | Adhambek | 1982. Electrification Plan | 10 Jan 2015 17:19 | 1 |
|
