最近ネットワークフローにハマっている（？）ので，勉強したことを書きます． 一応競プロに役に立つ可能性がなくはないです． あと，簡単のために詳細な数学的議論を省略しているところがあります． TL;DR 最小費用流問題は一般化すると双対関係が綺麗に書け…

最近，最短路アルゴリズムについて新しく知ったことがあるのでメモ． 内容にそんなに自信はないので間違っているかも． グラフ 上の二点間の最短路問題と言えば 辺の長さが全て非負→Dijkstra法 負の長さの辺がある→Bellman-Ford法 というような使い分けを行…