「グラフを変形して、〜となる最小量を求めよ、〜とならない最大量を求めよ」系はヤバイ問題の宝庫というイメージがあり、それらをいつかやるリストとして挙げてみる。
完全に備忘録
AOJ 2230 How to Create a Good Game
DAG があたえられて、2 点 s-t 間の Longest Path の重みが変更されない範囲内で、各辺の長さを増やすとき、その増加分の総和の最大値
AOJ 2736 Longest Shortest Path
重み付き有向グラフがあたえられて、各辺 につき、長さを 1 増やすのに必要なコスト
が与えらえている。予算
の範囲内で s-t 最短路の長さを最大化せよ。
ラグランジュ双対などしたり、色々やばいこともあるみたい (参照)。
hos さんのスライドにある有名問題
連結な重み付き無向グラフ と
のある全域木
が与えられる。
の各辺の重みを修正して、
が最小全域木となるようにしたい。各辺の修正量の絶対値の和を最小化せよ。
色々いつかちゃんと勉強するリスト
- じょうしょうツリー
- 花火 (とこはるさんの記事の方針でやると、じょうしょうツリーもシンプルに解けるらしい)
- 手持ち花火 (ここなど)
- JOI2016 春合宿「最悪の記者2」
- KUPC2016 H「壁壁壁壁壁壁壁」
- こどふぉのなにか
- AOJ 2865 Farm Village
- AOJ 2396 Skyland
- AOJ 1385 Homework (2017 年 ICPC Asia , DEGwer さんがポリマトロイド交差に帰着して殴ったりしていた)
- POJ 2595 Min-Max (LP 双対とか)
- POJ 1275 Cachier Employment (牛ゲー)
- UTPC 2013 Asteroids2 (牛ゲー)
- UTPC 2012 きたまさの逆襲 (ラグランジュ双対)
参考
- 双対性 (wata さん)
- 競プロとLP双対まわりの話で最近知ったこと (とこはるさん)
