作者justlike68 (DAY)
看板Grad-ProbAsk
标题[理工] 交大101资演
时间Sat Jan 13 20:34:36 2018
大家晚安
有几题资演想请教~
20.
(58)
http://i.imgur.com/TShP2Xu.jpg
想问(58)题的C为什麽是对的呢?
Ford-Fulkerson复杂度不是|f*|E吗，应该跟capacity无关?
19.
http://i.imgur.com/O2UOidz.jpg
http://i.imgur.com/71MWKtm.jpg
想问的是
promblem1是在说哪个问题?
problem2是TSP吗?(TSP可以让每条边加权值是1?)
problem3是LP吗?(LP可以让每条边加权值是1?)
(57)的D是什麽诡异的叙述!?不知道怎麽问，但就是...想问xd
17.
(51)
http://i.imgur.com/InGHWGN.jpg
这题也是很诡异，怎麽看出他可以化成D选项的呢?
(E)又是哪里错?为什麽无法表示全部?
先谢谢各位了~祝大家考试顺利
-----
Sent from JPTT on my Samsung SM-J710GN.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.238.62.206
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1515846879.A.B5E.html
※ 编辑: justlike68 (36.238.62.206), 01/13/2018 20:36:10
1F：推 qaswed101: 58.C) 我认为是: f*是最大流量，而minimum cut <->flow 01/13 22:02
2F：→ qaswed101: 达到capcity。又flow加起来= capacity. D)每边的cap 01/13 22:02
3F：→ qaswed101: acity 都不同，不一定min cut就唯一。 01/13 22:02
4F：推 qaswed101: 57)prob1:我觉得是TSP 因为他说degree at most 2, 又想 01/13 22:18
5F：→ qaswed101: 到Hamilton cycle过每点之恰两边 01/13 22:18
6F：推 pinchieh1996: 题组19. 分别是HP/Shortest-path/Longest-path 01/13 22:22
7F：→ justlike68: 感谢楼上各位大大 01/14 18:10
8F：→ justlike68: 我再想想看 01/14 18:10