题意: 货币兑换,n,m,s,v 分别是货币所有的种类,m条语句,s是自己拥有的那一种货币,v是自己拥有的那种货币的数量(quantities)
下面的六个数是兑换币 被兑换币 正汇率,正手续费,反汇率,反手续费,问你到最后通过兑换自己的钱数能不能增加。
方法:要使自己的钱数通过
AC代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <stdio.h> 2 #include <string.h> 3 #define INF 0x3f3f3f3f 4 int n,m,a,b,v; 5 double c[200][200],r[200][200],v1,dis[300],u,w,x,s,flag; 6 void init() 7 { 8 for(int i=1; i<=n; i++) 9 { 10 dis[i]=0;//松弛条件为尽量大时应初始化为0,反之应为INF 11 } 12 dis[v]=s; 13 } 14 void Bellman( )//贝尔曼福特算法:外循环n-1次,每次都把所有的可以松弛的节点松弛一遍;n-1次的原因是由于每次内循环都会把该松弛的松弛掉, 15 //如果最短路存在的话,最长也就是n-1条边,所以外循环是n-1次。。还有一个重要原因是,一个节点最多被其他n-1个节点松弛。。。 16 { 17 for(int i=0; i<n; i++) 18 { 19 int mark=0; 20 for(int j=1; j<=n; j++) 21 { 22 for(int k=1; k<=n; k++) 23 { 24 if(dis[k]<((dis[j]-c[j][k])*r[j][k])) 25 { 26 dis[k]=(dis[j]-c[j][k])*r[j][k]; 27 mark=1; 28 } 29 } 30 } 31 if(mark==0) 32 { 33 break; 34 } 35 } 36 flag=0; 37 for(int i=1; i<=n; i++)//检查是否有正/负环,如果有的话,还能进行松弛操作 38 { 39 for(int j=1; j<=n; j++) 40 { 41 if(dis[j]<((dis[i]-c[i][j])*r[i][j])) 42 { 43 dis[j]=(dis[i]-c[i][j])*r[i][j]; 44 flag=1; 45 } 46 } 47 } 48 } 49 int main() 50 { 51 while(~scanf("%d%d%d%lf",&n,&m,&v,&s)) 52 { 53 init(); 54 for(int i=1; i<=m; i++) 55 { 56 scanf("%d%d%lf%lf%lf%lf",&a,&b,&u,&v1,&w,&x); 57 r[a][b]=u; 58 c[a][b]=v1; 59 r[b][a]=w; 60 c[b][a]=x; 61 } 62 Bellman(); 63 if(flag==1) 64 { 65 printf("YES "); 66 } 67 else 68 { 69 printf("NO "); 70 } 71 } 72 return 0; 73 }