https://i.imgur.com/CU5Boiy.jpg
https://i.imgur.com/nOSpSel.jpg

想問第12題組26題的e選項(答案有e)
我沒理解錯的話，在作ford algo前會讓整個graph的edge capacity整數化，這樣才能預估a
lgo完成時間，因此這個選項是說先找出max flow後會再normalize，所以有non-integral也
可以的意思嗎？

這選項是對的嗎？ 如果圖都存整數要怎麼變出小數？

我跟樓上有一樣的疑問

https://reurl.cc/xEb0NN答案是可以擁有非整數的Edge，只不過現實不會用倒是

原來如此@@

喔 我大概知道了可以有非整數edge（隨便畫個圖就能知道）但是肯定不是用FFA找的

E是對的吧，根據題目給的演算法，算出來只會是趨近整數的小數？

感謝

E不用管題目的算法吧？

他題目都跟你說consider the following proposed algo了...

題目是很像FFA 但我想不到怎麼找出小數解joy你能舉個例子嗎？應該說 怎麼讓edge上出現小數你說的 趨近整數的小數 是怎麼得到的？

喔不是，我算錯了，但假設s,t中間只有一條capacity=1的路徑https://i.imgur.com/rMoGm7x.jpg這樣嗎？抱歉上面我的接近整數那個回答應該是錯的，但答案應該要有E

K = 0.5不會再進迴圈了吧我覺得 題目應該是想說augmenting path可以取小數反正他符合augmenting的規則也沒人說不能這麼做就像我上面說的那樣不然FFA實作上應該是取path上最小的edge來做這樣怎麼做都是整數可能我題目哪邊漏看 那就再麻煩補充

一開始K=1的時候會進while loop然後變0.5再跳出去

他是從capacity scaling algo改過來的演算法，所以加一個proposed。原版while的condition是找到沒有augmentingpath為止，但這個改成K>=1。所以求出的f 不一定是maximum flow，真正的maximum flow要考慮樓上講的情況。應該吧我也不確定><

喔 我看懂joy的圖了啊這就和我說的一樣他augmenting path減掉的不是path上的最小edge而是亂減一個數字這會導致出來的結果不是maximum flow問題是誰會這樣做XD

歐歐乾抱歉我錯了QQ ，原版也是寫K>=1。跑到k=1時，就相當於FFA，所以是max flow沒錯，m大本來講得才對，選項E應該只是想講augmenting path不一定只能整數，例如j大的圖示QQ 證明參考http://people.csail.mit.edu/moitra/docs/6854lec8.pdf

講是講不一定只能整數但是誰會沒事弄一個小數出來XDD

不知道，可能是出題教授的惡意？

感謝以上幾位