[問題案] Minimum cost b-flow

yosupo06 commented 4 years ago

種類が多すぎて大変

yosupo06 commented 4 years ago

Primal-Dual : O(FE log V), 負辺なし Primal-Dual + (Bellman-Ford 負辺解消) : O(VE + FE log V), 負辺あり負閉路あるとぶっ壊れる？ Cost-Scaling + Push-Relabel : O(maxflowにかかる計算量(=V^3など？) * log (VC)) (C=max edge cost), 負辺は？

yosupo06 commented 4 years ago

Cycle canceling系？ https://en.wikipedia.org/wiki/Minimum-cost_flow_problem

yosupo06 commented 4 years ago

最小費用最大流最小費用でF流す最小費用循環流

yosupo06 commented 4 years ago

https://snuke.hatenablog.com/entry/2017/06/07/115821 O((F + F') E log V)

MiSawa commented 4 years ago

とりあえず

minimum cost b-flow problem: $n$, $m$, $b_v$, $l_e$, $u_e$, $c_e$ が与えられるので, $f_e$ と $p_v$ で $l_e \le f_e \le ue$ $\sum{e = (v, *)} fe - \sum{e = (*, v)} f_e = b_v$ $f_e > l_e \Rightarrow c_e - p_u + p_v \le 0 \forall e=(u, v)$ $f_e < u_e \Rightarrow c_e - p_u + p_v \ge 0 \forall e=(u, v)$ $|p_v| \le 10^{15}$ となるものを出力せよ. $n \le 100$ $m \le 1{,}000$ $|b_u|, |l_e|, |u_e|, |c_e| \le 10^9$ $l_e \le u_e$ 条件を満たす解が存在する

あたりで一つ作ってみようかと思うんですが, どうでしょうか. オプションとしては

復元無しで値だけ (↑の制約だとオーバーフロー)
出力をフローだけにする
負費用や負閉路を無くす
解の存在を保証せずに "infeasible" (もしくはカットを表す頂点集合) を出力させる
制約をいじってその他諸々のアルゴリズムを落としたり通したりする

などがあります. SSP/Primal-Dual は上の制約で落とせますが, ちょっと弄って容量スケーリングにすれば計算量が改善する ($O(m \log F \mathrm{SP^+}(n, m, C))$, 例えば普通の二分ヒープの Dijkstra 法で $O(m^2 \log F \log n)$) のでまぁいいかなという気があります. ($10^3$ で既にギリギリ感がありますが) 辺数を $10^4$ とかにすると, 計算量的には容量スケーリングでも厳しくなりますが, 実際落とすケースを作れるかどうかがよくわからんですね.

yosupo06 commented 4 years ago

提案ありがとうございます！

想定解について: 何を想定解法にしたいかと、そのオーダー(と、欲を言えば参考文献)をここに書いておいていただけると問題を解く人が助かり、嬉しいです。ジャッジの性質上通常の競プロでは想定解法に採用されないようなアルゴリズムでも大丈夫です。

計算量について: 遅い解法(今回だとSSP/Primal-Dual)が通ることは別にこのジャッジでは問題ないので、あまり落とすことは意識しなくて大丈夫です。もちろん制約が大きいほどチューニングに使いやすいので、想定解法の計算量から自然と思えるなかの最大、ぐらいが好ましいです。

yosupo06 commented 4 years ago

理想を以下に述べますが、基本的に準備を大変にする方向なので、大変すぎたら教えて下さい

復元無しで値だけ (↑の制約だとオーバーフロー)

https://judge.yosupo.jp/problem/shortest_path 復元はあったほうがいいと思います。また、基本的に値 + 復元両方、がこのジャッジのベースです(ref: https://judge.yosupo.jp/problem/shortest_path)。なので値も出力させたいです(int128なら許容範囲です)

出力をフローだけにする

悩ましいところです。まあ両方出させていいかなと思います

負費用や負閉路を無くす

無くさなくていいと思います

解の存在を保証せずに “infeasible” (もしくはカットを表す頂点集合) を出力させる

カットを表す頂点集合は出力させなくていいと思いますが、"infeasible"は欲しいです

MiSawa commented 4 years ago

諸々了解です, とりえあず作ろうとしてみてから詳細を詰めます.

Expected solutions:

Capacity scaling algorithm: $O(m \log U \mathrm{SP}^+(n, m, C))$.
Cost scaling algorithm: $O(n^3 \log(nC))$ or similar.
Network simplex algorithm: Depends on the pivoting strategy, exponential in the general algorithm although they're fast in practice.

where

$U$ is the max value of $|b_v|$, $|l_e|$, $|u_e|$,
$C$ is the max value of $|c_e|$,
$\mathrm{SP}^+(n, m, C)$ is number of operations of any single source shortest path algorithm on a graph of n vertices, m edges where the costs are nonnegative and less than $C$. e.g. $O(m + n \log n)$ with Dijkstra + Fibonacci heap, $O(m + n \log C)$ with Dijkstra + Radix heap. Though $O(m \log n)$ algorithm should be sufficient in this problem.

All of the available algorithms are explained (at least briefly) in Z. Király and P. Kovács, Efficient implementations of minimum-cost flow algorithms.

yosupo06 commented 4 years ago

色々バリエーションのある問題ですが、かなりの部分を網羅する問題が追加されたので一回閉じます / I close this issue because we added the general problem about mincostflow https://judge.yosupo.jp/problem/min_cost_b_flow

yosupo06 commented 3 years ago

https://old.yosupo.jp/submission/32518

コストをn + 1倍じゃなくてn倍しても通る？

yosupo06 commented 3 years ago

自己ループでやられてしまう人が多すぎる(n=2)のでサンプルにあるとうれしい

MiSawa commented 3 years ago

https://old.yosupo.jp/submission/32518

コストをn + 1倍じゃなくてn倍しても通る？

n 辺から成るサイクルで合計コストが -1 のものがあるグラフが入力の時に、運が悪いと落ちると思います。具体的には、アルゴリズムの実行中に、このループの残余容量が正で、ループの全ての辺が簡約コスト-1な状況になると死。

yosupo06 / library-checker-problems

[問題案] Minimum cost b-flow #143