作者tank123zzz (哇呼呼)
看板Grad-ProbAsk
标题Re: [理工] 交大101资演
时间Fri Jan 10 22:57:55 2020
※ 引述《justlike68 (DAY)》之铭言：
: 大家晚安
: 有几题资演想请教~
: 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.
想问一下55-57的那个题组的problem 2
为什麽是shortest path呢
选项还说可以用floyd解
可是他要求visit exactly once
这样floyd能解吗？
-----
Sent from JPTT on my Sony G3426.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.255.127.115 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1578668277.A.987.html
1F：→ DLHZ: shortest path还会visit两次吗? 01/10 23:03
因为想说p3说at most once
exactly once 不是所有点都要一次的意思吗
※ 编辑: tank123zzz (111.255.127.115 台湾), 01/10/2020 23:12:21
※ 编辑: tank123zzz (111.255.127.115 台湾), 01/10/2020 23:12:42
2F：→ cry589036511: 最短路径一定最多经过各点一次，exactly once代表 01/10 23:46
3F：→ cry589036511: 图上要有hp才成立，所以可用floyd找是否有长度v-1 01/10 23:46
4F：→ cry589036511: 路径存在 01/10 23:46
5F：→ DLHZ: 喔喔看错了 他的exactly once指的是经过的点 而不是所有点 01/10 23:51
6F：→ DLHZ: 就是有没有长度为K的simple path 01/10 23:54
好的 感谢两位
※ 编辑: tank123zzz (101.12.44.191 台湾), 01/11/2020 10:13:16