No.119

最小カット問題に帰着させる.

国ごとにノード $X_i, Y_i$ を用意し, $(s \rightarrow X_i, X_i \rightarrow Y_i, Y_i \rightarrow t)$ をそれぞれコスト $(B_i, \infty, C_i)$ の辺でつなぐ.

さらに, $i$ 番目の国のツアーに参加したときに $j$ 番目のツアーに参加しなければいけないとき, $X_i \rightarrow Y_j$ をコスト $\infty$ の辺でつなぐ.

あとはこのグラフの最小カットを求める.

グラフをカットするためには $s \rightarrow X_i, Y_i \rightarrow$ のどちらかまたは両方を切る必要があり, $s \rightarrow X_i$ だけ切った場合は $i$ 番目の国に行ってツアーに参加しない場合であり, $Y_i \rightarrow t$ だけ切った場合は $i$ 番目の国に行ってツアーに参加する場合であり, 両方切った場合は $i$ 番目の国に行かない場合となる.