※ 引述《saladim (殺拉頂)》之銘言：
: : 中文 最小費用最大流
: : 英文 minimum cost maximum s-t flow 古代文獻經常省略s-t
: : 我猜你看到的是 中文 最小費用流 的SSPA演算法。那是不一樣的主題。
: : 英文 minimum cost flow
: http://perso.ens-lyon.fr/eric.thierry/Graphes2010/amaury-pouly.pdf
: 我看的是這個, 就是因為如同內文提到, 這提可以用另一種解法, 就想說一起看看證明
: 是長什麼樣子, 沒想到不只樣子有差, 連要怎麼轉化都有點疑惑.
跟我猜的一樣，你看的這篇標題就寫著 minimum cost flow 啊。
不一樣的兩個問題，無論你怎麼轉化都轉不過去。
: 另一種解法在UVA 的forum還有一個本質相同 但是我想是另一種變形的方式,
: 另外看不出來cost在每個iteration有變化是因為每個arc的e.cost並沒有變化阿?
: ( http://mycodebattle.com/2014/10/UVa-10806/ )
int u = ed;
while (u != st)
{
edges[p[u]].flow += a[ed];
edges[p[u] ^ 1].flow -= a[ed];
u = edges[p[u]].from;
}
return true;
剩餘容量變了，圖上多出許多反方向的邊，也就是負的cost的邊。
: 這邊指的cost是指走過arc的cost, 而不是total cost. 這也是理論裡面說每個
: iteration需要變化的地方 所以我想是哪裡理解錯誤吧?
你看的文獻就不對，要怎麼跟你討論？
但是你說的大致上是正確的，
無論是 最小費用流 還是 最小費用最大流 的SSPA都是如此。
: 另外我還會去看一下 最小費用流 跟 最小費用最大流的差別 ORZ
建議你找英文的資料，因為中文網路上幾乎沒有人把這件事搞清楚，尤其是競賽選手。
圖論算法強者tarjan有寫一本網路流的書，
它裡面有稍微提到 minimum cost maximum flow，
可以加減參考看看。
https://books.google.com.tw/books?id=m1rAB3uWwBwC
: 懇請解惑~~
: 謝謝~