JOI 13春合宿 Presents(難易度8)
・小課題1はbit全探索でとれる
・まず, 連結成分ごとに分けて考える
・するとなもりグラフ(閉路が1個しかない)になっている
・閉路以外の頂点については貪欲に決めてよい(自分があげるプレゼントを調整することで最適に出来る)
・閉路内の頂点について考える.
・ある閉路について, 始点を1と仮定して貪欲にコストの高い方をとっていく
・もし閉路の終点から始点について貪欲にやってもそのまま最適解が得られるならOK, そうでないなら一つ選んで最適じゃない方にする(ここは貪欲を用いる)
・このようにすると解くことができた.
実装は閉路を上手に検出することが必要である. これは今回のようなグラフ(ある頂点からある頂点までの辺が一本しかなく, 入次数・出次数ともに1以下)の場合DFSせず, 繰り返しによって実現できる. 先に条件を無視した場合の貪欲の答えを計算しておき, 後から貪欲ではできない部分を除くのが最適である.
メモ: 閉路検出ライブラリ化する