Bellman-Ford变形 Currency Exchange POJ

题意：货币交换，有n种货币，m个货币兑换的地点，每一个地点提供两种货币的兑换且每一个地点的汇率不同，需要手续费，Rab(一单位货币a可以兑换货币b的数量）

现如今有货币s共有数量t,要求判断是否可以通过兑换使得货币s增加。如果图中有一个正权回路，可以通过这条回路不断增加某种货币的值，最后在增加货币s的值。

Bellman-Ford可以判断有没有负权回路。

建图，判断有没有正权回路。

//Bellman Flody判断有没有负边权
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f
using namespace std;
int n,m,s,g;
double t;
int u[300],v[300];
double r[300],c[300],d[105];
int Bellman()
{
    memset(d,0,sizeof(d));
    d[s]=t;//d[i]表示i种货币最多可以有d[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<g;j++)
    {
        if(d[v[j]]<(d[u[j]]-c[j])*r[j])
        {
            if(i==n) return 1;
            d[v[j]]=(d[u[j]]-c[j])*r[j];
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m>>s>>t;
    g=1;
    while(m--)
    {
        int x,y;
        double r1,c1,r2,c2;
        cin>>x>>y>>r1>>c1>>r2>>c2;
        u[g]=x,v[g]=y,r[g]=r1,c[g]=c1;//从u到v的汇率
        g++;
        u[g]=y,v[g]=x,r[g]=r2,c[g]=c2;
        g++;
    }
    if(Bellman()) printf("YES
");
     else printf("NO
");
}