PROBLEM LINK:
Author: Pawel Kacprzak
Tester: Misha Chorniy
Editorialist: Pawel Kacprzak
DIFFICULTY:
MEDIUM
PREREQUISITES:
Graph theory, Minimum Spanning Tree, Kruskal’s algorithm
PROBLEM:
This problem is all about Minimum Spanning Tree, which we call MST here. For a given graph G with N vertices and M weighted edges, the goal is to handle Q queries. Each query can either assign 0 weight to given existing edge in G or assign to a given edge its original weight, or ask for the weight of MST of the current graph G.
QUICK EXPLANATION:
Take a closer look at how does Kruskal’s algorithm work and notice that the answer for each query asking for the weight of the current MST can be computed by running Kruskal’s algorithm only on edges with zero weight and edges in the initial MST of G.
EXPLANATION:
Subtask 1
In the first subtask we have N \leq 200, M \leq 2000 and Q \leq 2000, so we can just keep track of the current weights of the edges while performing queries and for each query asking for the weight of the current MST, we can run any fast algorithm computing MST from the scratch, for example Kruskal’s algorithm. This solution has time complexity of O(Q \cdot f(N, M)), where f(N, M) is the complexity of used MST algorithm on a graph with N vertices and M edges. Notice that this results in O(Q \cdot M \cdot \log^*(M)) time for Kruskal’s algorithm even when full sorting is performed only at the beginning.
Subtasks 2 and 3
In these subtasks we have N \leq 2000, M \leq 2 \cdot 10^5 and Q \leq 20000.
The following approach can be used to solve both of these subtasks, the only difference is that in the last subtask one have to handle restoring original weights of edges, which is just a little bit more straightforward implementation.
Let’s first compute MST of the initial graph before performing any queries and let T be this MST. The crucial observation is that at any point while handling the queries, the weight of the MST of the current graph can be computed by running Kruskal’s algorithm on edges with zero weight at this point and edges of T.
Why is this observation correct? Well, if we take a closer look at how does this algorithm work, we can see that it iterate over a list of given edges in ascending order of their weights and put the current edge into the result if and only if it connects not yet connected components of G. So if we run it on edges with zero weight and edges from T, it will merge some components using some of these zero edges first and then try edges from T if necessary. Since the algorithm is only merging components, it follows that no edge not it T with non-zero edge at this point will be used by the algorithm, because after processing edges with zero weights, some edges from T might not be needed, but if any two components still require to be merged, the algorithm will do it with an edge from T just as it did in the initial graph.
Thus in order to solve the problem, one can maintain the list of edges with zero weights updating it when necessary - this can be done in O(1) time if for example a linked list is used, and for each query asking for the weight of the current MST run Kruskal’s algorithm on at most O(Q + N) edges. Theoretically this results in O(Q \cdot (Q + N) \cdot \log^*(N)) complexity, but notice that in order for K zero edges to be processed by the algorithm, we have to perform K queries adding them first, so the factor of Q^2 is divided by some constant of at least 4 here.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.