[理工] 资演交大101 第16题 ching4562 PTT批踢踢实业坊

楼主: ching4562 (monster710623) 2020-01-10 14:59:41

https://i.imgur.com/lDGnQVK.jpg
问一下这题在做什么啊
就我的理解好像是在找longest path 吗?
然后为何46题是c

作者: cossetannie (paa) 2020-01-10 15:06:00

找最小瓶颈路径吧从s出发每次都只走weight最小的边就是最小瓶颈路好像不是这样还是等大神来回答好了对啊那条路上权重最大的边就是瓶颈这问题应该等价于最大流问题都在找最小瓶颈

作者: zuchang (chang) 2020-01-10 15:27:00

shortest path吧啊不对critical path /work

作者: b10007034 (Warren) 2020-01-10 18:12:00

的确是longest path定义，对过枫叶本定义了按照这个逻辑的话，只差验证解Dijkstra的instance为什么不能拿DP解，E的time complexity比c大，所以inefficient等等我看错了，怎么又max又smallest

作者: mistel (Mistel) 2020-01-10 18:48:00

应该是bottle neck 但不知道min bottleneck tree生出来的tree是不是bottleneck path

作者: jeremyyuan (阿元) 2020-01-10 19:02:00

这是minimax path 可用Dijk修改relex function求得=>greedyhttps://reurl.cc/alKe1Y

作者: mi981027 (呱呱竹) 2020-01-10 22:58:00

作者: gash55025502 (白影弓) 2020-01-10 23:30:00

感谢楼上大大用心翻译XD

作者: mistel (Mistel) 2020-01-11 00:10:00

再请教一下这样bottleneck path是不是反过来定义就好了？用题目的定义方法的话就是W(P)=min_i=0~k-1{(wi,wi+1)}求max W(P)这样？

作者: jeremyyuan (阿元) 2020-01-11 00:30:00

回楼上对的 maximin path 就是 bottleneck path

作者: mistel (Mistel) 2020-01-11 08:31:00

感谢j大大

作者: mathtsai (mathtsai) 2020-01-11 19:41:00

不就只是找path上最大的edge吗这题应该是用MST来解

作者: jeremyyuan (阿元) 2020-01-11 21:05:00

回楼上要用MST也没错 minimax path可以在两点间的MST找到但这题不是在找MST 也不是edge 他是找path

作者: FRAXIS (喔喔) 2020-01-12 06:53:00

先找 MST 这样任两点间就可以在 MST 上有 path 了

继续阅读