感覺(jué)最短路好神奇呀，剛開(kāi)始我都 沒(méi)想到用最短路

題目：http://poj.org/problem?id=1860

題意：有多種從a到b的匯率，在你匯錢(qián)的過(guò)程中還需要支付手續(xù)費(fèi)，那么你所得的錢(qián)是 money=（nowmoney-手續(xù)費(fèi)）*rate，現(xiàn)在問(wèn)你有v錢(qián)，從s開(kāi)始出發(fā)交換錢(qián)能不能賺錢(qián)

題解：這題其實(shí)是用bellman_ford的思想，通過(guò)n-1次松弛后，如果還能增加，就說(shuō)明有環(huán) 可以使金錢(qián)數(shù)不斷增加。

1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<stack> 6 #include<queue> 7 #include<cmath> 8 #include<algorithm> 9 using namespace std; 10 int cnt; 11 double dis[1000]; 12 double n,m,v; 13 struct node 14 { 15 int u,v,next; 16 double r,c; 17 }edge[1000]; 18 19 void add(int u,int v,double r,double c) 20 { 21 edge[cnt].u=u; edge[cnt].v=v; 22 edge[cnt].r=r; edge[cnt++].c=c; 23 } 24 int bellman_ford(int s) 25 { 26 int i,j; 27 for(i=0; i<n; i++) 28 dis[i]=0; 29 dis[s]=v; //跟最短路不一樣，到自己的距離是原來(lái)的錢(qián)數(shù) 30 for(i=0; i<n-1; i++) 31 for(j=0; j<cnt; j++) 32 { 33 if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)//逆用最短路 34 dis[edge[j].v]=(dis[edge[j].u]-edge[j].c)*edge[j].r; 35 } 36 for(j=0; j<cnt; j++) 37 if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)//如果成立說(shuō)明有能使錢(qián)數(shù)增加的環(huán) 38 return 1; 39 return 0; 40 } 41 int main() 42 { 43 int s,i,j,a,b; 44 double rab,cab,rba,cba; 45 scanf("%lf%lf%d%lf",&n,&m,&s,&v); 46 cnt=0; 47 for(i=0; i<m; i++) 48 { 49 scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba); 50 add(a,b,rab,cab); 51 add(b,a,rba,cba); 52 } 53 if(bellman_ford(s)) printf("YES\n"); 54 else printf("NO\n"); 55 return 0; 56 } 57

?這個(gè)博客：http://blog.csdn.net/wangjian8006/article/details/7871753

就是到s的距離大于v了，就是YES。

有spfa的代碼，這個(gè)應(yīng)該理論上更省時(shí)間

轉(zhuǎn)載于:https://www.cnblogs.com/bfshm/p/3245933.html

總結(jié)

以上是生活随笔為你收集整理的poj 1860 Currency Exchange (最短路bellman_ford思想找正权环 最长路)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。