MinCostFlow

AOJ2230: How to Create a Good Game

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2230LP双対の問題。似たような問題でLongest Shortest Pathがあるのでそれの解説スライドを見ながら考察した。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2736 まず最長距離の双…

AOJ 2266: Cache Strategy

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2266箱が1つなら簡単。 箱がmつの時はM-1個の箱がコストを節約するために使えると考えられる。 どれくらいコストを節約できるか考えよう。 あるボールを時刻sに入れ、次に入れる時刻をtとしよう。…

POJ 3680: Intervals

http://poj.org/problem?id=3680解法は蟻本にある。蟻本では負辺にあらかじめ目一杯流すことで対応しているが、ここではベルマンフォードで最初のポテンシャルを求めることによって解いてみよう。ポテンシャルh(v):=(s-v間の最短距離)と基本的にすれば良いが…

POJ 2195: Going Home

http://poj.org/problem?id=2195これも最大マッチングに毛を生やした程度。 最小コスト完全マッチング問題とか言われるやつ。namespace MCF(Minimum Cost Flow)を使っているのだがMFと書きがちなので注意。 nt H, M; int HX[MAX_N], HY[MAX_N]; int MX[MAX_N…

POJ 3068: "Shortest" pair of paths

http://poj.org/problem?id=3068POJ 2135(蟻本p214)とほぼ一緒。 ただ今度は点も共有してはいけないので点の数を二倍にして、点の間に容量1、コスト0の辺を張って対処する。最大点素パスに毛が生えたくらい。inf = 2^30にしたらオーバーフローしてビビった。…