ainta's blog

By ainta, 5 years ago, ,

I found a problem about dynamic MST.

To solve it, I read this paper.

But I cannot understand it(Is it divide-and-conquer?)

Please help me plz T.T

• +5

 » 5 years ago, # | ← Rev. 2 →   0 At first you can try to solve it by sqrt-decomposition:1) Divide all queries to sqrt(max(n,m,k)) blocks.2) In each block firstly add all edges that will be modified in block (denote it S) to mst in any order, and then try to add edges not from S one by one in non decreasing order to mst. If edge not from mst will be added then it should be in any mst in block, so you can merge the ends of that edge and make the number of vertexes equal to O(blockSize).3) Now you should try to add edges not from S in non decreasing order to mst. Then each edge that will not be added to mst can't be in mst in block. So you can remove that edges and make number of edges equal to O(blockSize).4) Finally you can simply build mst for each query in O(blockSize * alpha) time.Okay. To get faster solution let's do the same in divide and conquer manner over queries: every time when we entering our solve function we should make the size of graph equal to the number of queries that we should process in function. So we have solution with complexity O(n * log^2n), cause we should sort the edges in block. Actually it's difficult to get complexity O(n logn) (I've not can) cause in paper authors telling us that we should firstly change all edges length by their numbers in sorted list of all lengths and then sort edges with integral lengths in O(numberOfEdges) time, but in that case we will get the constant about 16 or 32, cause the length of array will be different each time from (1 to n).
 » 4 months ago, # | ← Rev. 3 →   +6 Is it possible to solve this question online? Like for example, using a link-cut? Thanks.: I realised the link to the problem above isn't working so, here's a rough outline of the qn.So u have a graph with some edges. Then there are some queries, after each query an edge weight changes, and u are supposed to output the cost of the current mst. (the change continues from that query onwards, (not just within that single query))U can submit here but problem statement is in chinese (https://www.lydsy.com/JudgeOnline/problem.php?id=2001)This problem is offline, and can be solved with the method mentioned above, but I'm just wondering if an online solution exists. :)
•  » » 4 months ago, # ^ |   +4 I think this is the problem from the blog post. https://codeforces.com/problemsets/acmsguru/problem/99999/529Also, I can't read Chinese, but Google Translate leads me to believe that this blog talks about maintaining dynamic MST with LCT. https://www.cnblogs.com/flashhu/p/9498517.htmlCould someone elaborate on the idea (if it is actually possible, of course).
•  » » » 4 months ago, # ^ |   +3 If you start with a tree (as opposed to starting with no edges), then you when you are given an edge $e$ from $u$ to $v$ of cost $c$, you can find the maximum value edge on the path from $u$ to $v$ and if its value is greater than $c$, you can replace it with $e$, obtaining a tree with a smaller cost. All of these operations can be done with a LCT. Here is a possible implementation.
•  » » » » 4 months ago, # ^ |   +3 You are not given an edge, you are given edge weight updates.
•  » » » » 4 months ago, # ^ |   +3 It sounds like LCT can support dynamic MST with insertions but not deletions (or edge updates, since an update can be thought of as a deletion and an insertion).
•  » » 4 months ago, # ^ |   +4 There is an online solution that works in $O(m^{1/2})$ query time. This algorithm uses top trees. I don't know it, but I heard it have many applications in dynamic graph algorithms. The best known bound is $O(\log^4 n)$ amortized per query. This would be impossible to phrase as a competitive programming task, but I think it's an interesting read?