作者ben4562002 (Bin)
看板Grad-ProbAsk
标题[理工] 离散 ch8. 最小切集
时间Tue Dec 17 17:37:16 2019
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1576575438.A.17B.html
1F:推 pyramidinc: 我不会离散的labeling 方法 只会画residual network 12/17 17:52
2F:→ pyramidinc: 如果从这个角度来看的话 因为a到c 还有路 所以d 和 f 12/17 17:52
3F:→ pyramidinc: 可以透过c抵达 我的想法是这样 12/17 17:52
4F:→ pyramidinc: 有错还请其他人指正 12/17 17:53
5F:→ zuchang: 最大流量=最小切集 你就找哪条切线流量是10就好 12/17 19:06
6F:→ zuchang: A->z 这种方向才要算 所以ef 那条2不算 12/17 19:07
7F:推 mi981027: min cut在maxflow mincut thm的证明里有说明找法 12/17 20:00
8F:→ mi981027: 基本上就是s在residual network里能走到的点都归在S 剩 12/17 20:00
9F:→ mi981027: 下就在T 12/17 20:00
11F:→ ben4562002: 谢谢三位高手解惑xd用residual network去分两个集合 12/17 21:57
12F:→ ben4562002: 瞬间就懂了~ 12/17 21:57