最大フロー最小カット定理を用いて解くこともできます。

求める答えは以下のように生成されるグラフの \(S\) から \(T\) への最大フローとして定式化できます。

• カレー \(i\) に対応する頂点 \(A_i (1 \leq i \leq N)\), ライス \(j\) に対応する頂点 \(B_j (1 \leq j \leq M)\) および頂点 \(S\), \(T\) を用意する。

• \(S\) から各 \(A_i\) に流量\(A_i\) の辺を張る。

• 各 \((A_i,B_j)\) に流量 \(1\) の辺を張る。

• 各 \(B_j\) から \(T\) に流量\(B_j\) の辺を張る。

このグラフは \(O(NM)\) 辺あるので直接最大フローを求めることはできませんが、最大フロー最小カット定理よりこれは \(S\), \(T\) 間の最小カットと等しいです。この値を求めることを考えます。

\(S\), \(T\) 間のカットは、\(S\), \(T\) 以外の各頂点を、 \(S\) が属する頂点集合 \(S\) と \(T\) が属する頂点集合 \(T\) のどちらか一方に割り当てる方法にあたります。

カットのコストは次のように表されます。

(\(T\) に属する \(A_i\) の和) \(+\) (\(S\) に属する \(B_j\) の和) \(+\) (\(S\) に属する\(A_i\) の個数) \(\times\) (\(T\)に属する\(B_j\)の個数)

コストの最小化を考えるとき、\(A_i\) の降順に \(c\) 個を \(S\) 、 それ以外の \(N-c\) 個を \(T\) に割り当てるとしてよいです。

\(c\) を決め打つと、コストの式の第1項が定まります。また第2項と第3項への寄与を考えることで、\(B_j\) を \(S\) に所属させる場合のコストが\(B_j\)、\(T\)に所属させる場合のコストが \(c\) となります。よって \(\sum_{j} \min(B_j,c)\) が求まればよいです。

\(c\) を \(1\) ずつ大きくしたときの \(\sum_{j} \min(B_j,c)\) の変化を適切に管理することで、カットのコストの最小値を求めることができます。

時間計算量は \(O(N \log N + M \log M)\) や \(O(N \log N + M)\) です。

実装例