No.177

最大フロー問題である.

始点 $s$, 終点 $t$, $N$ 個 $G_i$, $M$ 個の $S_i$ のノードを用意し, 以下の通りノードをつなぐ.

• $s$ から $G_i$ に重み $J_i$ のノードをつなぐ.
• $S_i$ から $t$ に重み $C_i$ のノードをつなぐ.
• 原画マン $i$ と作画監督 $j$ が合う場合, $G_i$ から $S_j$ に重み $\infty$ のノードをつなぐ.

あとはこのグラフの最大フローが $W$ より大きいかどうかを調べればいい.