search

habara-k / ICPCLibrary

https://habara-k.github.io/ICPCLibrary/
3 stars 0 forks source link

最小費用流が負辺に対応していない #28

Closed habara-k closed 3 years ago

habara-k commented 4 years ago

primal dual のポテンシャルの初期化でdijkstraを回しているため, 最初に負辺があるとポテンシャルを正しく計算できない.

habara-k commented 4 years ago

http://sigma425.hatenablog.com/entry/2014/10/12/122018 蟻本に書いてあるらしい.

kanra824 commented 3 years ago

参考その2 https://snuke.hatenablog.com/entry/2017/06/07/115821

habara-k commented 3 years ago

そもそも負辺を貼らない！流量が決まってるので一律でコストを足して、後で引けば良いので