作者zxm20243 ( )
看板b98902HW
标题[离散]P123
时间Tue Jan 11 15:30:39 2011
我不确定这个看法是不是对的
所以丢上来请问大家QQ
补真相
http://tinyurl.com/4c34njv
对於所有可能存在的F，都应该要满足P121的式子
由等号右边得知F <= c(S)
考虑每种存在F，S的切法有很多，所以F要满足每种c(S)
既然每种c(S)都要满足，所以对於最小的c(S)仍然要满足
也就是说，当我们找到一种F = c(S)时
我们就找到了min c(S)
(假设不是min c(S)，那麽这个F必然>min c(S)，矛盾)
同理，也就是我们找到了Maximum flow
不晓得这个解释OK不OK
先感谢大家的指教了QQ
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.249.34
1F：推 gn00499901:基本上没错吧，挑毛病的话就是：F必然">"min c(S) 01/11 16:12
2F：→ gn00499901:当然写">="逻辑也没错啦，因为我们已经假设不会"=" 01/11 16:14
已修正，感谢乌龟>////<
因为老师讲义上的结论下太快了跟不上QQ
所以想要确定一下我这样想对不对@@
※ 编辑: zxm20243 来自: 140.112.249.34 (01/11 16:19)
3F：推 jessica1338:这个会有问题吗?@@ 01/11 18:38
4F：推 pinkyenyen:这位同学好会猜题喔！ 01/13 23:10