yukicoder No.119 旅行のツアーの問題
最小カットを最大フローに言い換えて解くタイプの問題に挑戦してみました．おそらくフローを使った簡単な応用問題だとは思うのですが，初めて触れたので発想が斬新だと感じました．(この記事はフローを学んで2日目の記事です，間違いがあれば遠慮なく指摘してください．まだフローを知らない方は記事の後半から見た方がいいかもしれません．)
問題：No.119 旅行のツアーの問題 - yukicoder
解法：まずはこの手の問題が最小カットを使えば解ける問題と見抜く実力が必要．とはいいつつ，yukicoderにはタグという超助かる機能が存在するので，今回はそれを前提として解きました．問題には「最大の満足度」とあるので最小カットに適用できるように「最小の満足損失」に言い換えます．
ここではサンプル1を例に説明します．問題文から，ある国には「ツアーに参加しかつ訪れる」「ツアーに参加しないが訪れる」「ツアーに参加しようがしまいが訪れない」の3種類の扱いをすることができます．それぞれについて，ツアーに参加し訪れる場合は，ツアーに参加せず訪れる場合は
，訪れない場合は
の満足度を得ることができます．損失に言い換える際は，損失0が3種類の選択の中で最も満足度が高い数字(つまり
)とします．つまり各選択肢は損失に言い換えると順に
，
，
となります．下の表はサンプル1の場合の各国，各選択肢の損失です．
| 国 | ツアー参加 | ツアー参加せず | 訪れない |
|---|---|---|---|
| 0 | 0 | 10 | 20 |
| 1 | 20 | 0 | 50 |
唐突ですが，次のような有向グラフを考えます．
例えば国0のツアーに参加し，国1には訪れないという場合，次のようなカットで表現します．
このようにしていろいろカットを試して最小になったものが満足度最大の国の行き方であるといえます． ただ，この問題には複数の組み合わせにおいて，「国Cをツアーで訪れた場合，国Dはツアーしないで訪れるということができない」という制約が存在します．例えばサンプル1では「国0をツアーで訪れた場合，国1はツアーしないで訪れるということができない」と解釈します(ここの辺りが問題文を1回縦読みするとよく分からなくなってしまうところであり，少し作為的な気もします)．これをグラフとカットを用いて表現します．つまり，サンプル1において
「国0をツアーする」かつ「国1をツアーしない」を実現するカットは存在しない
と表現することができます．つまり下の図のようなカットはありえません．
ただ，その他の組み合わせにおけるカット(通り)は実現可能でなければいけません．そこで下の図のようにコスト
の有向辺を張ります．
すると，上手い具合に1通りの成立してはいけないカットの合計コストがになり，最小カットとはなりえないことが確認できると思います．他の8通りのカットは今まで通りの合計コストとなります(この部分の辺を張ったり辺を入れ替えたりして上手いグラフを作るのは試行錯誤がある程度必要な部分ですが，分かると楽しいです)．
Max-flow Min-cut Theoremより，最小カットは最大フローと同じなので，SからTに流せる最大のフローをDinicなどのアルゴリズムで求め，求まった最小損失を最大満足度に言い換え直せばOKです．
ここからは自分がこの問題に取り組む前にやった事前準備について書いておきます．
まずフローを知らなかったので(学部の授業で触れたことはあるけれど，忘却の彼方に行ってしまった)，色々なページを参考にしました．フローの定義や最大フローを求める過程，各アルゴリズムに関しては下のページが詳しかったです．
http://hos.ac/slides/20150319_flow.pdf
アルゴリズム(Dinic)の実装は有名な蟻本を参考にしました．(当たり前ですが証明を読んだり，アルゴリズムの吟味をしたりしたこともあって，ここまでの理解が結構時間かかりました)
次にAOJの最大フローをストレートに聞いてくる問題とyukicoderのフローの基本問題を解きました．
No.177 制作進行の宮森あおいです！ - yukicoder
その後に下のスライドを見つけてどうやらフローを使った面白い解き方があるということで，No.119に取り組んだという順です．
www.slideshare.net
フローをこれから学ぼうとしている方は参考になるかもしれないと思って，あとがきとしました．
