poj 1860 Currency Exchange (最短路bellman_ford思想找正权环 最长路)

时间：2025-03-18 19:34:08

感觉最短路好神奇呀，刚开始我都 没想到用最短路

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

题意：有多种从a到b的汇率，在你汇钱的过程中还需要支付手续费，那么你所得的钱是 money=（nowmoney-手续费）*rate，现在问你有v钱，从s开始出发交换钱能不能赚钱

题解：这题其实是用bellman_ford的思想，通过n-1次松弛后，如果还能增加，就说明有环 可以使金钱数不断增加。

 #include <iostream>

  #include<cstdio>

  #include<cstring>

  #include<cstdlib>

  #include<stack>

  #include<queue>

  #include<cmath>

  #include<algorithm>

  using namespace std;

  int cnt;

  double dis[];

  double n,m,v;

  struct node

  {

      int u,v,next;

      double r,c;

  }edge[];

  void add(int u,int v,double r,double c)

  {

      edge[cnt].u=u; edge[cnt].v=v;

      edge[cnt].r=r; edge[cnt++].c=c;

  }

  int bellman_ford(int s)

  {

      int i,j;

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

      dis[i]=;

      dis[s]=v;  //跟最短路不一样，到自己的距离是原来的钱数

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

      for(j=; j<cnt; j++)

      {

          if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)//逆用最短路

          dis[edge[j].v]=(dis[edge[j].u]-edge[j].c)*edge[j].r;

      }

      for(j=; j<cnt; j++)

         if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)//如果成立说明有能使钱数增加的环

          return ;

      return ;

  }

  int main()

  {

      int s,i,j,a,b;

      double rab,cab,rba,cba;

      scanf("%lf%lf%d%lf",&n,&m,&s,&v);

      cnt=;

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

      {

          scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);

          add(a,b,rab,cab);

          add(b,a,rba,cba);

      }

      if(bellman_ford(s)) printf("YES\n");

      else printf("NO\n");

      return ;

  }

这个博客：http://blog.****.net/wangjian8006/article/details/7871753

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

有spfa的代码，这个应该理论上更省时间

相关文章