[理工] 離散 ch8. 最小切集

看板Grad-ProbAsk作者 (Bin)時間6年前 (2019/12/17 17:37), 編輯推噓2(2推 0噓 10→)
留言12則, 4人參與, 6年前最新討論串1/1
https://i.imgur.com/SJdyCsO.jpg
https://i.imgur.com/VcJWrzL.jpg
請問這題的minimum cut為何可以切出{a, b, d, f}為一組呢？ d跟f滿了應該要被排除在外(吧?) 感謝幫助解惑的各位了！ ---- Sent from BePTT on my Sony G8142 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.164.177 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1576575438.A.17B.html
推
12/17 17:52, 6年前 , 1F
我不會離散的labeling 方法 只會畫residual network
12/17 17:52, 1F
→
12/17 17:52, 6年前 , 2F
如果從這個角度來看的話 因為a到c 還有路 所以d 和 f
12/17 17:52, 2F
→
12/17 17:52, 6年前 , 3F
可以透過c抵達 我的想法是這樣
12/17 17:52, 3F
→
12/17 17:53, 6年前 , 4F
有錯還請其他人指正
12/17 17:53, 4F
→
12/17 19:06, 6年前 , 5F
最大流量=最小切集 你就找哪條切線流量是10就好
12/17 19:06, 5F
→
12/17 19:07, 6年前 , 6F
A->z 這種方向才要算 所以ef 那條2不算
12/17 19:07, 6F
推
12/17 20:00, 6年前 , 7F
min cut在maxflow mincut thm的證明裡有說明找法
12/17 20:00, 7F
→
12/17 20:00, 6年前 , 8F
基本上就是s在residual network裡能走到的點都歸在S 剩
12/17 20:00, 8F
→
12/17 20:00, 6年前 , 9F
下就在T
12/17 20:00, 9F
→
12/17 20:01, 6年前 , 10F
12/17 20:01, 10F
→
12/17 21:57, 6年前 , 11F
謝謝三位高手解惑xd用residual network去分兩個集合
12/17 21:57, 11F
→
12/17 21:57, 6年前 , 12F
瞬間就懂了~
12/17 21:57, 12F
‣ 更多 ben4562002 的文章
文章代碼(AID): #1T-A7E5x (Grad-ProbAsk)