問題概要
各街に対し
- その街に行きツアーに参加
- その街に行きツアーに参加しない
- その街にそもそも行かない
が選べる.
上2個の選択には満足度が割り当てられており,得られる.
街に行かないなら満足度はその街からは得られない.
m個条件が与えられる.
x->yという条件(x<y)
xの街でツアーに参加するならyの街でもツアーに参加しないといけない
解答
燃やす埋める.
しかし,選択肢が3つあるのでうまく3つ目を組み込む.
街に行かない辺を切ると,その街に関わる条件をガン無視できることを意識すると以下のような辺の生やし方ができる.これはサンプル3
i->i'の辺を切ると,その街にそもそも行かないということ
提出
感想
最高におもしろい. 燃やす埋めるの中身を理解してないと解けなさそうなので非常に良い. 生きていてよかった