PROBLEM LINK:Author: Trung Nguyen Tester: Suchan Park Editorialist: Suchan Park DIFFICULTY:MediumHard PREREQUISITES:How to construct minimum spanning trees + Very advantageous if you know what GomoryHu 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$ mincut 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 GomoryHu 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$ mincut 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 $st$ mincust cost, and check whether $A = B$. Then, how to compute the matrix $B$? By some prior knowledge or googling, one can find GomoryHu Tree can solve the exact same problem. What is a GomoryHu tree? Given a graph $G$, the algorithm produces a tree $T$ that has the exact same mincut 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$ mincut 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$ mincut 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$ mincut 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 mincut 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 $AH$ has mincut 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 maximumweight 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 $AD$, $DF$ and $FA$. 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:
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 mincut cost is already decided and is larger than $uv$. How do we know if the mincut 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, $uv$ is guaranteed to be included in the optimal tree. (since it is nonsense to increase all the other edges to make $uv$ nonmaximum) So, the edge is included in the solution tree, which means mincut cost between $u$ and $v$ is fixed to $A_{u, v}$. By repeating this argument, now we know when the mincut 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 (mincut cost of $u$ and $v$) $ A_{u, v}$. And we know when the mincut 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 nonascending 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 mincut cost easily (for example, using DFS). Print out the difference between the sum of two matrices (input, and mincut 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.
This question is marked "community wiki".
asked 21 May, 17:09

In fact, obvious constraint A[i][k] >= min(A[i][j], A[j][k]) is sufficient. Many O(n^3) solutions use this observation passed. answered 23 May, 21:33

The link for Practice/Contest is redirecting to CHSIGN. answered 21 May, 21:24

After reading BlanCode's unofficial editorial for this problem, which seems to have been taken down meanwhile, I wrote up a formal proof of how and why the solution laid out there works, to try and fill in the gaps in BlanCode's very lucid explanation and make it clear to myself. In case anyone is interested: PDF answered 01 Jun, 03:01
