POJ1860Currency Exchange（SPFA）

时间：2022-01-14 04:52:06

http://poj.org/problem?id=1860

题意：  题目中主要是说存在货币兑换点，然后现在手里有一种货币，要各种换来换去，最后再换回去的时候看能不能使原本的钱数增多，每一种货币都有对应的汇率，而货币A到货币B的汇率即为1货币A换得得货币B的数量，但兑换点是要收取佣金的，且佣金从源货币中扣除，例如，你想在汇率29.75，佣金为0.39的兑换点把100美元换成卢布，得到的卢布数即为（100-0.39）*29.75 = 2963.3975.

样例解释：

3 2 1 20.0

1 2 1.00 1.00 1.00 1.00

2 3 1.10 1.00 1.10 1.00

多组输入，第一行中N代表有N种货币可以互相兑换，M代表有M个货币兑换点，S代表这个人手中的的货币的编号，V代表这个人手中拥有的货币数量，底下M行

每行六个数，A,B代表可以交换的货币A和B，剩下的实数RAB,CAB,RBA,CBA，代表A到B的汇率，佣金，B到A的汇率，佣金。以某种兑换方式增加原本的钱数，而且必须兑换为原来的货币。

解法：用spfa和Bellman都可以，我用的是spfa，改了一下原模板就过了

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 int u,v,w;

 const int maxn = ;

 const int maxm = ;

 const int oo = <<;

 struct node

 {

     int u;

     int v;

     double x,y ;

     int next;

 }edge[maxm];

 double dis[maxn];

 int m,n,num;

 double ount;

 int head[maxn],cnt,sum[maxn];

 int vis[maxn] = {};

 queue<int>qu;

 void add(int u,int v,double x,double y)

 {

     edge[cnt].u = u ;

     edge[cnt].v = v ;

     edge[cnt].x = x ;

     edge[cnt].y = y ;

     edge[cnt].next = head[u];

     head[u] = cnt++ ;

 }

 int spfa(int s)

 {

     for(int i =  ; i < m ; i++)

     {

         dis[i] = ;

         vis[i] =  ;

     }

     dis[s] = ount;

     qu.push(s);

     vis[s] =  ;

     while(!qu.empty())

     {

         int u = qu.front();

         qu.pop();

         vis[u] = ;

         for(int i = head[u] ; i != - ; i = edge[i].next)

         {

             int v = edge[i].v;

             if((dis[u]-edge[i].y)*edge[i].x > dis[v])

             {

                 dis[v] = (dis[u]-edge[i].y)*edge[i].x;

                 if(!vis[v])

                 {

                     vis[v] = ;

                     qu.push(v);

                 }

                 sum[v]++;

                 if(sum[v] > m)

                 return -;

             }

         }

     }

     return ;

 }

 void Init()

 {

     cnt =  ;

     memset(head,-,sizeof(head));

     memset(sum,,sizeof(sum));

     while(!qu.empty())

     qu.pop();

 }

 int main()

 {

     while(scanf("%d %d %d %lf",&m,&n,&num,&ount)!=EOF)

     {

         Init();

         int u,v;

         double x,y,xx,yy ;

         for(int i =  ; i < n ; i++)

         {

             scanf("%d %d %lf %lf %lf %lf",&u,&v,&x,&y,&xx,&yy);

             add(u,v,x,y);

             add(v,u,xx,yy);

         }

         if(spfa(num) > )

         cout<<"NO"<<endl;

         else cout<<"YES"<<endl;

     }

     return ;

 }

http://blog.csdn.net/lyy289065406/article/details/6645778

这个大神用的是Bellman

相关文章