Hello, I have been trying to solve a problem from a Gym Contest (http://codeforces.net/gym/100484/attachments — 100484G — Highways). It seems like an straightfoward Kruskal implementation to me. At first, I was using a vector to store all the edges, but that resulted in MLE in testcase 21. Only then I came to realize N could be upto 10^4, and there's no way to store 10^4 * 10^4 edges without getting a MLE veredict.
Is there an heuristic or data structure to quickly calculate the minimum distance between all the points and generate the MST of the given graph?
why you want to store 10^4 * 10^4 edges the maximum number of edges you need to store is 10^4 edge
you do not need to store it , just calculate it every time . Also kruskal will not work in this problem cause u cannot sort 10^8 edges . so use prim with arraylist implementation
what's the wrong with kruskal why you need to store 10^8 edge ?
As far as i can remember , here , there are 10^4 nodes . and 10^5 edges are given that i "cannot" take and i have to make a spanning tree . So total choice of edge can be at most 10^8 — min(0,10^5) . In kruskal i need to take each edge and sort them ascending in weight , which here is not possible
As they are 10^4 nodes, there are 10^8 possibles edges to generate a MST with Kruskal. As far as I know, you need to have all the edges and sort them with increasing weight or cost. After that you greedily choose the edges that won't generate a cycle or loop on the MST.
Dup Post D:
Thank you. I should've thought about implementing Prim's algorithm on this one as it will be avoid storing all the edges, and I will just need to calculate the minimun. I think I was blocked as I already solved a similar version of this problem with a lower N ( 2 < N <= 750).