This problem can be rephrased as follows.

Consider a graph \(G\) whose vertex set is \(V:= \{X_1,\ldots,X_H,Y_1,\ldots,Y_W\}\) and whose edge set is \(E:=\{(X_i,Y_j)\mid \text{Square }(i,j)\text{ has a piece}\}\).
For each edge, the cost \(c:E\to \mathbb{N}\) is defined as \(c((X_i,Y_j))=\text{the cost of piece in Square }(i,j)\).
Find the weighted minimum edge cover.

(The method below intuitively consider “how much we can reduce the cost than ‘choosing the piece with the minimum cost in each row and each vertex.’”)

Consider determining the edge set that forms a edge cover by choosing the edges through the following two steps.

1. Choose an arbitrary subset \(E_1\) of \(E\).
2. For each vertex \(v\) that is not adjacent to any edge belonging to \(E_1\), choose the edge adjacent to \(v\) with minimum cost, allowing duplicates, and let \(E_2\) be the union of \(E_1\) and those edges. (\(E_2\) results in a multiset.) Then \(E_2\) is a edge cover of \(G\).

Since we can arbitrarily choose \(E_1\), it is obvious that the optimal solution is included in those which can be constructed by this procedure. Also, in the optimal solution, we can assume that any pair of edges in \(E_1\) do not share endpoints (we can prove that, if there exists such pair, we may remove one of them from \(E_1\) without increasing the ultimate cost). Therefore, when finding the optimal solution, we may constrain \(E_1\) to those in which no pair of edges does not share endpoints.. Moreover, \(E_2\) is obviously uniquely determined by \(E_1\), we may only consider how to determine \(E_1\).

What is the cost for the edges determined by these steps? Let \(C_v\) be the minimum cost of edge adjacent to Vertex \(v\), and let \(V_1\) be the set of vertices that is an endpoint of any edge in \(E_1\), then
\(\sum_{e\in E_2}c(e)=\sum_{e\in E_1}c(e)+\sum_{v\in V\setminus V_1}C_v.\)
Here, defining \(c':E\to \mathbb{Z}\) by \(c'((u,v))=c((u,v))-C_u-C_v\), we have
\(\sum_{e\in E_1}c(e)+\sum_{v\in V\setminus V_1}C_v\\ =\sum_{v\in V}C_v+\sum_{e\in E_1}c(e)-\sum_{v\in V_1}C_v\\ =\sum_{v\in V}C_v+\sum_{e\in E_1}c'(e).\)
Since the first term is a constant independent of \(E_1\), we may minimize the second term. Since \(E_1\) can be any edge set that does not share an endpoint, the second term is the minimum weight matching on \(G\) where the cost is assigned by \(c'\). Since \(G\) is a bipartite graph, it can be found as the minimum cost flow.

Minimum cost matching on bipartite graph containing negative-cost edges

Construct the following graph.

• Add an edge from \(S\) to each \(X_i\) with capacity \(1\) and cost \(0\)
• For each \((X_i,Y_j)\), add an edge from \(X_i\) to \(Y_j\) with capacity \(1\) and cost \(c'((X_i,Y_j))\)
• Add an edge from each \(Y_i\) to \(T\) with capacity \(1\) and cost \(0\)

The minimum cost of arbitrary amount of flow from \(S\) to \(T\) is the desired answer. However, if there exists an edge with negative cost, we cannot find the answer fast. Instead, taking a sufficiently large constant \(BIG\), we consider the following graph.

• Add an edge from \(S\) to each \(X_i\) with capacity \(1\) and cost \(0\)
• For each \((X_i,Y_j)\), add an edge from \(X_i\) to \(Y_j\) with capacity \(1\) and cost \(BIG + c'((X_i,Y_j))\)
• Add an edge from each \(Y_i\) to \(T\) with capacity \(1\) and cost \(0\)

In the new problem, an excessive cost \(BIG\) per unit flow is imposed than the original problem. Therefore, the desired answer is \(\min_i(P_i-i*BIG)\), where \(P_i\) is the minimum cost for flow \(i\).

This can be computed efficiently with slope method in ACL (AtCoder Library).

Sample code (C++)

Alternatively, we may add an edge from \(S\) to \(T\) with capacity \(\min(H,W)\) and cost \(BIG\) and find the minimum cost of flow \(\min(H,W)\) to find the answer in the same way.

Sample code (C++)