学步园

有N种货币，M个货币兑换点，每个兑换点只支持两种货币的兑换，每次兑换需支付手续费

现在有第S种货币V元，问能否经过若干次兑换后得到的第S种货币能否增值，即大于V

这是Bellman-Ford求最小路径的变形，如果能通过兑换是货币增值，则从源点S出发，再回到S时，V[S]，变大有两种情况：

1.从S出发，回到S的路径中，除最外圈的环外，有一正环，使得可以通过这个正环得到无穷多的钱

2.从S出发，回到S的路径中，只有一个环，使得回到S时可以增值

这时，我们需要改变松弛条件，由上界松弛，改为下届松弛，情况1下，可以无限松弛，但只要有一轮松弛后,V[S]>V，即可退出

情况2下，松弛次数有限，当不能松弛时，即可退出，然后判断V[S]是否大于V

通过1860和3259两道题，对Bellman-Ford算法的理解更深入了

代码：

#include<iostream><br /> using namespace std;<br /> #define MAX 101<br /> #define inf 0x3f3f3f3f<br /> //#define eps 1e-8<br /> double d[MAX];<br /> int n,m,s,cnt;<br /> double v;<br /> struct node<br /> {<br /> int u;<br /> int v;<br /> double c;<br /> double w;<br /> }p[2000];<br /> int Bellman_Ford()<br /> {<br /> int i,j,flag;<br /> memset(d,0,sizeof(d));<br /> d[s]=v;<br /> while(d[s]<=v)<br /> {<br /> flag=1;<br /> for(j=1;j<=cnt;j++)<br /> {<br /> if(d[p[j].v]<(d[p[j].u]-p[j].c)*p[j].w)<br /> {<br /> d[p[j].v]=(d[p[j].u]-p[j].c)*p[j].w;<br /> flag=0;<br /> }<br /> }<br /> if(flag)<br /> return d[s]>v;<br /> }<br /> return 1;<br /> }<br /> int main()<br /> {<br /> int i,j,x,y;<br /> double ra,rb,ca,cb;<br /> cin>>n>>m>>s>>v;<br /> cnt=0;<br /> while(m--)<br /> {<br /> scanf("%d %d %lf %lf %lf %lf",&x,&y,&ra,&ca,&rb,&cb);<br /> p[++cnt].u=x;<br /> p[cnt].v=y;<br /> p[cnt].w=ra;<br /> p[cnt].c=ca;<br /> p[++cnt].u=y;<br /> p[cnt].v=x;<br /> p[cnt].w=rb;<br /> p[cnt].c=cb;<br /> }<br /> if(Bellman_Ford())<br /> {<br /> printf("YES/n");<br /> }<br /> else<br /> {<br /> printf("NO/n");<br /> }<br /> return 0;<br /> }