この問題は、次のように読み替えられます。

\(V:= \{X_1,\ldots,X_H,Y_1,\ldots,Y_W\}\) を頂点集合、 \(E:=\{(X_i,Y_j)\mid \text{マス }(i,j)\text{ に駒がある}\}\) を辺集合 とするグラフ \(G\) を考える。
各辺に対してコスト \(c:E\to \mathbb{N}\) が
\(c((X_i,Y_j))=\text{マス }(i,j)\text{ にある駒のコスト}\)
と定まっているとき、\(G\) の最小重み辺被覆を求めよ。

（以下で述べる方法は、直観的に言えば「『各行・各列で一番コストが小さい駒を選ぶ』という方法からどれだけコストを削減できるか」を考えています）

辺被覆となる辺集合を、辺を次のような \(2\) ステップに分けて決めることを考えます。

1. \(E\) の部分集合 \(E_1\) を自由に決める。
2. \(E_1\) に属するいずれの辺とも接続していない各頂点 \(v\) について、\(v\) と接続する最もコストの小さな辺を重複を込めて全て集め、\(E_1\) との合併をとったものを \(E_2\) とする(\(E_2\) は多重集合)。\(E_2\) は \(G\) の辺被覆である。

\(E_1\) を自由に決められることから、最適解はこの手順で構成できるものに含まれることは明らかです。また、最適解において、\(E_1\) に属する辺は端点を共有しないようにすることができます(もし端点を共有する辺の組が存在した場合、その一方を\(E_1\) から取り除いても、最終的なコストは増加しないことが示せます)。したがって、最適解を求めるとき、\(E_1\) はどの \(2\) 辺も端点を共有しないようなものに限って考えて良いです。さらに、\(E_2\) は明らかに \(E_1\) から一意に定まるので、\(E_1\) の決め方を考えさえすれば良いです。

このような手順で辺を決めたときのコストを考えてみます。頂点 \(v\) と接続する辺のコストの最小値を \(C_v\)、\(E_1\) に属するいずれかの辺の端点として登場する頂点を集めた集合を \(V_1\) とすると、
\(\sum_{e\in E_2}c(e)=\sum_{e\in E_1}c(e)+\sum_{v\in V\setminus V_1}C_v\)
となります。ここで、 \(c':E\to \mathbb{Z}\) を \(c'((u,v))=c((u,v))-C_u-C_v\) と定めると
\(\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)\)
となります。第 \(1\) 項は \(E_1\) に依らない定数なので、第 \(2\) 項を最小化すればよいです。\(E_1\) は端点を共有しない辺集合を自由に動くので、第 \(2\) 項は、\(G\) の辺にコスト \(c'\) を割り当てたときの最小重みマッチングになります。\(G\) は二部グラフだったので、最小費用流を用いて求めることができます。

コストが負の辺が存在するときの二部グラフの最小重みマッチング

次のようなグラフを作ります。

• \(S\) から各 \(X_i\) へ容量 \(1\) コスト \(0\) の辺を張る
• 各 \((X_i,Y_j)\in E\) に対し、\(X_i\) から\(Y_j\) へ容量 \(1\) コスト \(c'((X_i,Y_j))\) の辺を張る
• 各 \(Y_i\) から \(T\) へ容量 \(1\) コスト \(0\) の辺を張る

このグラフで \(S\) から \(T\) へ任意の流量を流した時の最小費が求める答えです。しかしコストが負の辺が存在するとき、そのままでは高速に求めることができません。そこで、十分大きな正の定数 \(BIG\) を取り、次のようなグラフを考えます。

• \(S\) から各 \(X_i\) へ容量 \(1\) コスト \(0\) の辺を張る
• 各 \((X_i,Y_j)\in E\) に対し、\(X_i\) から\(Y_j\) へ容量 \(1\) コスト \(BIG+c'((X_i,Y_j))\) の辺を張る
• 各 \(Y_i\) から \(T\) へ容量 \(1\) コスト \(0\) の辺を張る

新しい問題では、元の問題に比べ、流量 \(1\) あたり、余分に \(BIG\) のコストがかかるようになっています。したがって、流量 \(i\) の最小費用を \(P_i\) としたとき、\(\min_i(P_i-i*BIG)\) が求める答えになります。

これは ACL(Atcoder library)のslopeメソッドを使うことで効率的に求めることができます。

実装例(C++)

なお、\(S\) から \(T\) へ容量 \(\min(H,W)\) コスト \(BIG\) の辺を張り、流量 \(\min(H,W)\) の最小費用を求めることでも同様に求めることができます。

実装例(C++)