オンサイトで未確認

ukuku09の活動記録。

AOJ 2691: Cost Performance Flow

久々にフローの問題を解いたうくー!

 

……とは言っても本質であろう「解析的に解く」という考察はbeetくんに聞いたのでまぁはい。

 

問題概要

https://onlinejudge.u-aizu.ac.jp/#/problems/2691

 

辺に向きとコストと容量のついたグラフがあります。sからtへフローf_{s,t}を流します。このとき、

B(f_{s,t}):=C(f_{s,t})^2+(M-F(f_{s,t}))^2

で定義されるバランス関数B(f_{s,t})を最小化するf^*_{s,t}を求め、B(f^*_{s,t})を既約分数で出力してください。

ここで、Ms-tフローの最大流量を、C(f_{s,t})f_{s,t}のコストを、F(f_{s,t})f_{s,t}の流量を表します。

 

みたいな(日本語ができないので許して

 

解法

最小費用流(というかPrimal Dual)の気持ちになると解けます。

 

こういうのは解析的に解く(beet談)らしいので、B(f_{s,t})が下に凸の関数ならその極小値を求めたいです。(実際B(f_{s,t})は下に凸な関数です。)

ところで、C(f_{s,t})は流量F(f_{s,t})の関数とみなせるので、以降F(f_{s,t})FC(f_{s,t})C(F)と書きます。(ついでにB(f_{s,t})B(F)で書きます。)

Primal Dualで新たな最短経路に沿ってフローを流すたびに得られる、それまでの流量FとコストC(F)をグラフ(グラフ理論の方でない)にプロットします。

f:id:ukuku09:20180527113449j:plain

こんな感じになります。

最小費用流の気持ちになると、新しい最短経路に対して流量とコストは比例の関係にあるので、ある区間\alpha \le F \le \betaでは

\displaystyle C(F)=\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)

です。

この折れ線上にB(F)を最小化する点があるはずなので、上の式をB(F)に代入して微分します。

\displaystyle B(F)=\left\{\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)\right\}^2+(M-F)^2

\displaystyle B'(F)=2\frac{C(\beta)-C(\alpha)}{\beta-\alpha}\left\{\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)\right\}-2(M-F)

で、B'(F)=0として整理すると、

a=\beta-\alpha

b=C(\beta)-C(\alpha)

c=C(\alpha)

\displaystyle F=\frac{a^2M+b^2\alpha-abc}{a^2+b^2}

が得られるので、これが\alpha \le F \le \betaを満たすかを調べてえいえいすれば良いです。

どの区間も不等式を満たさないなら、プロットした点でのB(F)の最小値が答えです。

 

補足

答えを既約分数にしないといけないので、式変形とかしないといけないくて面倒くさいです。多分その辺を適当にやったからだと思うんですが、オーバーフローしたので†__int128_t†を使って無理やり通しました。

 

提出コード

AOJ 2691: Cost Performance Flow