poj 1860 Currency Exchange (spfa求最长路)

poj 1860 题目链接

题意:有n种货币,m个货币交易点,每个货币交易点只能是两种货币之间交换,给出两个方向的汇率和手续费。初始拥有数量v的货币s,问能否经过一些py交易,使得最后手里的货币s比v多。

思路:大概还是用spfa求最长路。。松弛那里需要注意一下算法。。。

1A。。。好爽啊。。。。。

 

poj 1932 XYZZY (floyd传递闭包+spfa求最长路)

poj1932题目链接

题意:初始在点1,有100点能量,然后每个点有一个能量值【-100,100】,经过某个点会加上这个点的能量值,问能否找到一条到点n且的路线,且路径任何点的能量值一直为正。一共不超过100个点。

 

思路:像样例中是直接联通,一路上的能量值都大于0,这是有解的一种情况。另一种是存在一个正环,可能一次路过后面的能量值不够,但是我们可以走多次啊。

因为要求每一步的能量值都大于0,那么我们可以初始化d[]数组为0,然后用spfa求最长路(只需要把那个三角形等式换个方向即可)

如果可以直接联通,也就是d[n]>0,那么有解。

还有可能是存在一个环(判断环的方法是用一个数组在spfa的时候统计每个点入队的次数,如果一个点的入队次数大于n,那么就存在环,且这个点在环中

但是我们还要保证起点1和终点n是经过这个环的。

所以先跑一发floyd. 其实n才100也算给了提示吧,不用floyd的话没道理这么小的数据。。?

感觉这道题很棒,把spfa和floyd结合在了一起。

学到了判断环的方法,spfa求最长路的方法,复习了传递闭包。