PROBLEM LINK:
Author: Trung Nguyen
Tester: Suchan Park
Editorialist: Suchan Park
DIFFICULTY:
Medium-Hard
PREREQUISITES:
How to construct minimum spanning trees + Very advantageous if you know what Gomory-Hu Tree is.
PROBLEM:
We want to increase some elements of a given matrix A so that there exists a graph G such that for all 1 \le i, j \le n, A_{i, j} equals to the i-j min-cut cost of G. What is the minimum possible total amount of increases?
QUICK EXPLANATION:
We can reduce the problem from graph to tree, from the theory of Gomory-Hu tree. After that, we can prove that the optimal graph for the given matrix is the maximum spanning tree.
EXPLANATION:
First, we have to think how to check whether there exists a graph G, such that for all 1 \le i, j \le n, the i-j min-cut cost of G equals to A_{i, j}. Let’s call this state as valid.
The easiest way one could think is to generate every possible graph G (although there are infinite amount of them), make a matrix B such that B_{s,t} equals to the s-t min-cust cost, and check whether A = B. Then, how to compute the matrix B? By some prior knowledge or googling, one can find Gomory-Hu Tree can solve the exact same problem.
What is a Gomory-Hu tree? Given a graph G, the algorithm produces a tree T that has the exact same min-cut cost for every possible pair of vertices s and t. Also, for every possible tree T, we can find a graph G such that when we give G as an input, the algorithm produces T – it is T itself.
This means, A is a valid matrix if and only if there exists a tree T, such that for all 1 \le i, j \le n, the i-j min-cut cost of T equals to A_{i, j}.
Usually, trees can be easily dealt than general graphs. Given a tree T, let’s try to compute the s-t min-cut cost. From the definition, we need to see all paths from s to t. But since T is a tree, the path between them is guaranteed to be unique. Therefore, s-t min-cut cost of the tree equals to the minimum weight over all edges on the path from s to t. (if we cut that edge, the path is disconnected)
Now, from this knowledge, let’s find an algorithm that checks whether A is a valid matrix. It is hard to think of it easily, so I drew an example tree and its min-cut cost matrix.
As you can see, there are lots of 1s in this matrix. Why? Since 1 is the minimum edge weight among all edges, so all pair of vertices whose paths pass A-H has min-cut cost 1.
On the other hand, there are only two 6s in this matrix, because 6 is the maximum edge weight among all edges, so no pair except (H, I) contains an edge whose weight is shorter than 6.
This gives a good insight. In both cases, we can find what edge is valid by looking at the shape of colored cells of the matrix, but it obviously seems easier to consider the edge with maximum weight.
Then, what if there are multiple maximum-weight edges? If you think for a while, you can notice that even in that case, 6s doesn’t appear too much.
Take a look at A-D, D-F and F-A. The matrix cells corresponding to those pairs are all 6, so how could we determine the tree? But… if you think more, you will notice that it is totally irrelevant, since nothing changes if we change the edges of the tree like:
This is because the set of path weights is guaranteed to be the same. So, from this example, we found out that any edge from that matrix that has maximum weight is guaranteed to be included, as long as it doesn’t make a cycle.
In conclusion, the algorithm which checks whether A is a valid matrix (and additionally generate a corresponding tree T) is:
- Consider the entries in the matrix in non-ascending order. Initially the T has no edges.
- Suppose we are considering edge u-v right now.
- If u and v are not connected in T, u-v is guaranteed to be inside T, so add u-v into T.
- Otherwise, nothing happens.
You can see the algorithm is surprisingly similar to Kruskal’s algorithm. And actually it is true, this algorithm just computes the maximum spanning tree of the graph made by the graph from A (A is the adjacency matrix) Therefore, the time required is O(N^2 \log N) (Kruskal’s) or O(N^2)(Prim’s).
Now, let’s go through our original problem. When do we want to increase the cost of edges? Clearly, if it is necessary. When is it necessary? Only if the min-cut cost is already decided and is larger than u-v. How do we know if the min-cut cost is already decided or not? Let’s see.
From the algorithm above, it is tempting to think about the maximum entry A_{u, v}, where A is the input. Do we have to increase A_{u, v}? Clearly not. This is because, since this has the maximum weight, u-v is guaranteed to be included in the optimal tree. (since it is nonsense to increase all the other edges to make u-v non-maximum) So, the edge is included in the solution tree, which means min-cut cost between u and v is fixed to A_{u, v}.
By repeating this argument, now we know when the min-cut cost is already decided – if and only if there is a path between u and v in the current tree. (exactly, forest) In that case, we can increase the edge cost by (min-cut cost of u and v) - A_{u, v}. And we know when the min-cut cost is undecided – if and only if there isn’t a path between u and v in the current tree.
In which order should we consider the entries – clear, in non-ascending order of entries! So, here, we are also computing the maximum spanning tree.
In conclusion: the maximum spanning tree of the given adjacency matrix is the optimal solution graph for this problem. After generating the tree, we can compute pairwise min-cut cost easily (for example, using DFS). Print out the difference between the sum of two matrices (input, and min-cut cost matrix of the optimal solution)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
