作者chchwy (mat)
看板Prob_Solve
标题Re: [问题] ACM 104
时间Mon Dec 1 22:31:03 2008
关於这题
我後来在uva论坛上找到了相当详尽的讲解
关於Modified Floyd-Warshall
http://online-judge.uva.es/board/viewtopic.php?t=7292
请有兴趣的人自行前往:D
※ 引述《chchwy (mat)》之铭言：
: 先附上题目
: http://online-judge.uva.es/p/v1/104.html
: 请教各位
: 我在写这题的时候，参考了Algorithmist上的解答
: http://www.algorithmist.com/index.php/UVa_104
: 网页上写说可以用修改过的 Floyd-Warshall Algo. 来解这题
: 顺便提出了一个新的递回公式
: d(i,j) = max{ d(i,k)*d(k,j) , d(i,j) } where i!=j
: 就我的理解，照上面这个公式最後解出来的d(i,j)应该是profit最大
: 但是题目要求的是：所有profit>1%的路径中，路径最短的那条。
: 请问这是怎麽回事呢?
: ps.网页上好像有稍微提到一下，但不是说得很清楚
: ps. 我是为了解这题才去学Floyd-Warshall
: 初学有理解不清的地方，还请各位多多指教~_~...
--
怀着一颗对这个家有无限关爱的心，我 再度流浪到远方。 --<舒伯特>
这些年来，我唱着歌，唱出爱，可是它对我来说却是痛苦；
我唱出痛苦，可是它对我来说又是爱。 爱与痛苦就这样分割着我。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 203.68.15.209