辺eにはコストd(e)と容量c(e)が定まっていて、sからtへ流量Fのフローを流したときの全ての辺の流量×コストの和が最小になる時の費用を求める問題。これは単純で、最大流のときとほぼ同じです。残余グラフを考えて、そこでコストを考慮して最短路に沿って流せ…