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

不知道，可能是出题教授的恶意？

感谢以上几位