首页 > 代码库 > Currency Exchange

Currency Exchange

2024-08-09 23:42:35   219人阅读

此题可以用bellman-ford算法来求解。bellman-ford算法是求解最短路径，此题是求解
“最大路径”，条件与松弛条件相反，因此求的是无限松弛的最大正权路径，可以用bellman-ford算法去解题。
此题中的“最大路径”其实就是求改变点数下是否有增加更新点。


我们用dis[i]来表示第i种货币的钱数。
我们求最大那么需将dis[i]初始话为0，再用bellman-ford算法来进行求解是否有增加的更新点。
假设我们从u点到v点（这里我们将每种钱币看成图中的一点）
则需求:
dis[v]<(dis[s]-Cs->v)*Rs->v

如果结果是true，则dis[v]=(dis[s]-Cs->v)*Rs->v,用flag表示是否更新的话，那么返回的flag就是true，否则返回false。

此题参考了网上大神的思想

代码：

#include <iostream>
#include <string.h>
using namespace std;
int N;//货币种类
int M;//交换点次数
int S;//货币持有类型
double V;//货币持有此类型的数量
//定义交换货币的结构体
struct{
    int a;//a货币
    int b;//b货币
    double C;//货币交换所需付的押金
    double R;//货币交换的汇率

}exec[202];
int all; //边数
double dis[101];//N不超过100，各种货币的钱数。
bool bellmanford()
{
    //初始化dis[exec[all].a-exec[all].C)*exec[all].R
    memset(dis,0,sizeof(dis));
    dis[S]=V;//因为输入时货币S是有钱数的。
    bool flag=false;
    for(int i=1;i<=N-1;i++)
    {
        for(int j=0;j<all;j++)
        {
            if(dis[exec[j].b]<(dis[exec[j].a]-exec[j].C)*exec[j].R)
            {
                dis[exec[j].b]=(dis[exec[j].a]-exec[j].C)*exec[j].R;
                flag=true;
            }
        }
        if(!flag)
            break;
    }
     for(int j=0;j<all;j++)
       if(dis[exec[j].b]<(dis[exec[j].a]-exec[j].C)*exec[j].R)
          return true;
    return false;

}
int main()
{
    //定义临时变量
    int a;
    int b;
    double rab;
    double cab;
    double rba;
    double cba;
   while(cin>>N>>M>>S>>V)
   {
       all=0;
       for(int i=0;i<M;i++)
       {
           cin>>a>>b>>rab>>cab>>rba>>cba;
           exec[all].a=a;
           exec[all].b=b;
           exec[all].R=rab;
           exec[all++].C=cab;
           exec[all].a=b;
           exec[all].b=a;
           exec[all].R=rba;
           exec[all++].C=cba;
       }
       if(bellmanford())
        cout<<"YES"<<endl;
       else
        cout<<"NO"<<endl;
   }
  return 0;
}


Currency Exchange


联系
我们