Official Analysis

Explanation

Since the official analysis is well-documented and covers the problem in its entirety, read that first. The following notes clarify a few details of the implementation.

• Firstly, note that the number of rows and columns is equivalent to $2N$, because the matrix is square. Therefore, when constructing our graph, we can simply add $N$ to distinguish row $i$ from column $j$.

Of course, the problem of finding a minimum weight cycle breaking edge set is equivalent to the well known problem of finding a maximum weight spanning forest of $G$, except that we would build the complement set of edges to keep rather than the set of edges to remove.

• Notice that the edges that we should remove - which are highlighted in the diagram in red - are equivalent to any edges that are not included in the maximum spanning tree of graph $G$. Therefore, our answer is equivalent to the difference between the total sum of all the edges and the those that are in the maximum spanning tree.

Implementation

Time Complexity: $\mathcal{O}(N^2\log N)$

Copy
 Code Snippet: C++ Short Template (Click to expand)

struct DSU {
	vi e;
	void init(int N) { e = vi(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);