POJ1860-Currency Exchange-判正环

两种货币的交换可以当成两条边，建图后跑Bellman_ford算法就好了。

Bellman_ford算法可以用来处理负边权，所以可以判断是否存在负环。反过来就可以判断是否存在正环。

 /*--------------------------------------------------------------------------------------*/

 //        Helica's header

 //        Second Edition

 //        2015.11.7

 //

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <ctype.h>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <string>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <map>

 //debug function for a N*M array

 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\

 {for(int j=;j<(M);j++){\

 printf("%d",G[i][j]);}printf("\n");}

 //debug function for int,float,double,etc.

 #define debug_var(X) cout<<#X"="<<X<<endl;

 /*--------------------------------------------------------------------------------------*/

 using namespace std;

 const int maxn = +;

 int N,M,T,S;

 int tol;

 double V;

 struct Edge

 {

     int u,v;

     double c,r;

 }E[*maxn];

 double dist[maxn];

 bool bellman_ford(int start,int n)

 {

     memset(dist,,sizeof dist);

     dist[start] = V;

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

     {

         bool flag = false;

         for(int j=;j<tol;j++)if(dist[E[j].v] < (dist[E[j].u]-E[j].c)*E[j].r )

         {

             dist[E[j].v] = (dist[E[j].u]-E[j].c)*E[j].r;

            flag = true;

         }

         if(!flag) return false;

     }

     for(int j=;j<tol;j++)

     {

         if(dist[E[j].v] < (dist[E[j].u]-E[j].c)*E[j].r)

             return true;

     }

     return false;

 }

 int main()

 {

     while(~scanf("%d%d%d%lf",&N,&M,&S,&V))

     {

         int a,b;

         double r1,r2,c1,c2;

         tol = ;

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

         {

             scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);

             E[tol].u = a;E[tol].v = b;

             E[tol].c = c1;E[tol++].r = r1;

             E[tol].u = b;E[tol].v = a;

             E[tol].c = c2;E[tol++].r = r2;

         }

         if(bellman_ford(S,N))

             printf("YES\n");

         else

             printf("NO\n");

     }

 }