けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

いずれちゃんと解きたい、やばいグラフ変形系問題やフロー系問題たち

「グラフを変形して、〜となる最小量を求めよ、〜とならない最大量を求めよ」系はヤバイ問題の宝庫というイメージがあり、それらをいつかやるリストとして挙げてみる。

完全に備忘録

AOJ 2230 How to Create a Good Game

DAG があたえられて、2 点 s-t 間の Longest Path の重みが変更されない範囲内で、各辺の長さを増やすとき、その増加分の総和の最大値

AOJ 2736 Longest Shortest Path

重み付き有向グラフがあたえられて、各辺  e につき、長さを 1 増やすのに必要なコスト  c_e が与えらえている。予算  P の範囲内で s-t 最短路の長さを最大化せよ。

ラグランジュ双対などしたり、色々やばいこともあるみたい (参照)。

hos さんのスライドにある有名問題

連結な重み付き無向グラフ  G G のある全域木  T が与えられる。 G の各辺の重みを修正して、 T最小全域木となるようにしたい。各辺の修正量の絶対値の和を最小化せよ。

色々いつかちゃんと勉強するリスト

参考