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

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

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

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

完全に備忘録

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 が最小全域木となるようにしたい。各辺の修正量の絶対値の和を最小化せよ。

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

  • じょうしょうツリー
  • 花火 (とこはるさんの記事の方針でやると、じょうしょうツリーもシンプルに解けるらしい)
  • 手持ち花火 (ここなど)
  • 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 きたまさの逆襲 (ラグランジュ双対)

参考