I'm trying to generate a testcase so that Prim with complexity $$$O(N^2)$$$ is significantly faster than Prim with priority queue $$$O((N + M)log(N + M)$$$ (Here $$$N$$$ is number of vertices and $$$M$$$ is number of edges).
However as I generate with random weight of the edges the two algorithm runs with nearly the same amount of time (I generate with $$$N = 2500$$$ and $$$M = N * (N - 1) / 2$$$ (As polygon doesn't allow bigger constraint)).
I wonder if there is a way to construct such test (that for example, the priority queue contains many elements while running...).
Thanks.
Are you able to provide the source code of your implementations? I suspect that you did not implement the first version correctly.
https://ideone.com/6O6oxw
This is the $$$O(N^2)$$$ version. The problem is to find the total weight of Minimum Spanning Tree.
Reading the input is slower than other standard operations. If the input size is $$$M$$$, you can assume that reading the input is $$$O(M \cdot \log M)$$$. With this assumption, you're trying to distinguish between two algorithms with same time complexity.
Try a compressed input like:
Thanks <3
pls let me get a new haircut
http://usaco.org/index.php?page=viewproblem2&cpid=946
This problem forced $$$\mathcal O(N^2)$$$ Prim's by setting $$$N \leq 7500$$$ and using an alternative scheme for generating the edge weights to get around input bottleneck. If you take this approach, make sure you pick a better edge weight function because this particular function allowed unintended $$$\mathcal O(1)$$$ solutions.
Thanks so much!
Unrelated, but how do you solve this in $$$\mathcal{O}(1)$$$?
https://usaco.guide/problems/usaco-946-i-would-walk-500-miles/solution
See solution 3
You can drive vertexes into 2 groups, and have small weights inside each one, and big weights from one to another.