$M$ が十分に小さければ、最大流問題で解ける。
ボール 箱
①--->① ボールと箱を結ぶ辺の容量は、頂点番号の積
A1↗ \＼ / ＼B1
／ \ × ↘
ⓢ X ②-B2-ⓣ
＼ / × ↗
A2↘ /／ \ ／B3
②--->③
でもさすがに $M=5 \times 10^5$ は無理。
なので、ボール-箱間のコストが法則的なことを使わないといけない。
最大フロー最小カット定理 より、最小カットの考え方で解く。
最小カットは、以下で定義される。
カットとなり得る辺を分類すると、以下のようになる。
| 分類 | 容量 |
|---|---|
| a) ⓢ-ボール間 | ボール頂点 $i$ が $T$ の時、$A_i$ |
| b) ボール-箱間 | ボール頂点 $i$ が $S$、箱頂点 $j$ が $T$ の時、$i \times j$ |
| c) 箱-ⓣ間 | 箱頂点 $j$ が $S$ の時、$B_j$ |
a) b) c)
↓ ↓ ↓
ボール 箱
● ● ○:Sに属する頂点
A1↗ ↗ ●:Tに属する頂点
／ /
ⓢ / ○-B2->ⓣ
/
/
○--->●
ここで、
とする。
$P,Q$ を固定した時のカットを式で表すと、以下になる。これを最小化したい。
真ん中のb)を示す項 $\sum_{i \in P}\sum_{j \in \overline{Q}}i \times j$ は、 分配法則によってまとめて $\sum_{j \in \overline{Q}} f(P) \times j$ とできる。
すると、式(1)の3項のうち右2項は $\sum_{j \in \overline{Q}} f(P) \times j + \sum_{j \in Q}B_j$ となり、各 $j$ は $Q$ と $\overline{Q}$ のどっちかには属するので、
結局、$f(P)$ が決められたとき「各 $j$ について $B_j,f(P)j$ のどっちか小さい方を選べばよい」ということになる。
左の1項 $\sum_{i \in \overline{P}}A_i$ を考える。これも、上記と同じく $f(P)$ を軸にまとめたい。
とすると、これは $N \times f(U)=O(N^3)$ のDPで事前計算できる。
すると、$f(\overline{P})=f(U)-f(P)$ なので、$f(P)$ を決めると求めることができる。
$f(P)$ を固定することでカットが計算できるようになったので、あとは実際に $f(P)=k$ として $k=0,1,...,f(U)$ を試す。
「$k \times j \gt B_j$ となるような $j$ の集合」を $Q$ として、
がカットとなり、全ての $k$ を試した上での最小値が答え。
$k$ が増加する毎に $Q$ は増えていく一方なので、
$f(\overline{Q})$ と $\sum_{j \in Q}B_j$ は、
はじめ $Q=\phi,\overline{Q}=V$ からはじめて順次 $Q$ に移していけばよい。
$k=\lfloor \frac{B_j}{j} \rfloor$ であるような $j$ を
$k$ の処理が終わったタイミングで $Q$ に移していけば、$k$ を全て試す過程を通して $O(M)$ で管理できる。
全体で $O(N^3+M)$