作者ching4562 (monster710623)
看板Grad-ProbAsk
标题[理工] 资演 交大101 第16题
时间Fri Jan 10 14:59:41 2020
https://i.imgur.com/lDGnQVK.jpg
问一下这题在做什麽啊
就我的理解好像是在找longest path 吗?
然後为何46题是c
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.217.110.114 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1578639583.A.8D4.html
1F：→ cossetannie: 找最小瓶颈路径吧01/10 15:06
2F：→ cossetannie: 从s出发 每次都只走weight最小的边就是最小瓶颈路01/10 15:13
3F：→ cossetannie: 好像不是这样 还是等大神来回答好了01/10 15:16
可是weight那边好像是max诶
※ 编辑: ching4562 (1.167.52.251 台湾), 01/10/2020 15:18:35
4F：→ cossetannie: 对啊 那条路上权重最大的边就是瓶颈01/10 15:20
5F：→ cossetannie: 这问题应该等价於最大流问题 都在找最小瓶颈01/10 15:20
6F：推 zuchang: shortest path吧01/10 15:27
7F：→ zuchang: 啊 不对01/10 15:30
8F：→ zuchang: critical path /work01/10 15:34
9F：推 b10007034: 的确是longest path定义，对过枫叶本定义了01/10 18:12
10F：推 b10007034: 按照这个逻辑的话，只差验证解Dijkstra的instance为什01/10 18:16
11F：→ b10007034: 麽不能拿DP解，E的time complexity比c大，所以ineffic01/10 18:16
12F：→ b10007034: ient01/10 18:16
13F：→ b10007034: 等等我看错了，怎麽又max又smallest01/10 18:38
14F：推 mistel: 应该是bottle neck 但不知道min bottleneck tree生出来的01/10 18:48
15F：→ mistel: tree是不是bottleneck path01/10 18:48
16F：推 jeremyyuan: 这是minimax path 可用Dijk修改relex function求得=>g01/10 19:02
17F：→ jeremyyuan: reedy01/10 19:02
所以这类minimax path问题是要求什麽啊
※ 编辑: ching4562 (219.91.74.143 台湾), 01/10/2020 21:43:26
※ 编辑: ching4562 (219.91.74.143 台湾), 01/10/2020 21:50:54
20F：推 gash55025502: 感谢楼上大大用心翻译XD01/10 23:30
21F：推 mistel: 再请教一下 这样bottleneck path是不是反过来定义就好了01/11 00:10
22F：→ mistel: ？ 01/11 00:10
23F：→ mistel: 用题目的定义方法的话就是W(P)=min_i=0~k-1{(wi,wi+1)} 01/11 00:10
24F：→ mistel: 求max W(P)这样？ 01/11 00:10
25F：推 jeremyyuan: 回楼上 对的 maximin path 就是 bottleneck path 01/11 00:30
26F：推 mistel: 感谢j大大 01/11 08:31
感谢楼上各位大神
※ 编辑: ching4562 (1.200.202.223 台湾), 01/11/2020 08:36:40
27F：→ mathtsai: 不就只是找path上最大的edge吗 01/11 19:41
28F：→ mathtsai: 这题应该是用MST来解 01/11 20:41
29F：推 jeremyyuan: 回楼上 要用MST也没错 minimax path可以在两点间的MST 01/11 21:05
30F：→ jeremyyuan: 找到 但这题不是在找MST 也不是edge 他是找path 01/11 21:05
31F：推 FRAXIS: 先找 MST 这样任两点间就可以在 MST 上有 path 了 01/12 06:53