PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 演算法 Ford-Fulkerson問題
作者:
liljimmy
(吉米)
2020-11-27 13:50:06
https://i.imgur.com/gj3EXz0.jpg
請問這題的B選項,題目說任意邊的capacity都是整數,推測選項意思應該是:執行Ford-Fu
lkerson找到一條augmenting path時,不一定要把他補滿可以只加任意flow,所以才會有可
能產生小數的flow在邊上,不知道這樣理解對不對?
https://i.imgur.com/OjFKR2m.jpg
這邊想問一下名詞””arc””的定義是什麼?
看答案推敲是指minimum cut上所有的邊都叫做arc嗎?
先謝謝各位高手。
作者:
mi981027
(呱呱竹)
2020-11-28 00:27:00
1. 不對 在capacity是整數的情況下用FF找到的一定是整數,這在CLRS有個定理只是最佳解本來就不一定要是整數,可以稍微畫個簡單的圖試試看,立宇的書裡應該也有例子
作者: liljimmy (吉米)
2020-11-28 11:13:00
@mi981027 感謝 那題了解了第二題的arc是什麼意思還是不會QQ
作者:
FRAXIS
(喔喔)
2020-11-28 13:27:00
arc 就是 edge
作者: liljimmy (吉米)
2020-12-01 11:01:00
@FRAXIS 那這邊他指的minicut s-t中的arcs就是指兩個集合之間所連結的邊嗎?那這題後面是要我們在上述這些「arcs」上capacity+1這樣嗎?抱歉還是不太懂
繼續閱讀
106台大資工 計組 roofline model
jimmylin1024
[理工] 101 清大 計算機科學 計科 13題
joywilliamjo
【理工】中央 107 奇異值分解
terry8575
[理工] 106中興電機 機率
ap15021
[理工] 徵求109中央資工解答
jeff62405
[理工] 藍算盤 P360 4.31題 2-issue processor
z598998599
[理工] 台大電子109年
chinij88
[理工] 103清大資工 Bottleneck Spaning Tree問
liljimmy
[理工] 103中央通訊機率
ap15021
[理工] 離散 林緯老師 5-3二項式係數 兩題
yee52590
Links
booklink
Contact Us: admin [ a t ] ucptt.com