POJ 1860 Currency Exchange(Bellman-Ford判断最长路是否含有正环)

题目链接：kuangbin带你飞 专题四 最短路练习 E - Currency Exchange

题意

有n种货币，你含有num面额的其中一种货币。
给定m种交易明细，即货币a和b之间的手续费与兑换率。双向兑换时，手续费与兑换率不一定相同。
求有没有可能，在多次兑换后你手中的货币大于num。

思路

以货币为点，交易情况为边，本题可转换为求最长路是否含正环的问题。
用Bellman-Ford，但要有所修改，原本松弛次数为n－1次，但本题可能有这种情况，给定图有正环，但需要多次迭代后才能大于初始金额，所以将松弛次数改为只要边权有更新，则一直松弛下去。直到大于初始金额。

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 109;
const int MAX = 0x3f3f3f3f;
struct Edge
{
    int u, v;
    double r, c;
}edge[N*2];

double d[N];
bool Bellman_Ford(int n, int e, int src, double num)
{
    for(int i=1; i<=n; i++)
        d[i] = 0;
    d[src] = num;

    while(d[src] < num + 1e-9)
    {
        bool flag = true;
        for(int i=0; i<e; i++)
        {
            int u = edge[i].u;
            int v = edge[i].v;
            double to = (d[u]-edge[i].c)*edge[i].r;
            if(d[v] + 1e-9 < to)
            {
                d[v] = to;
                flag = false;
            }
        }
        if(flag)
            return d[src] > num;
    }
    return 1;
}

int main()
{
    int n, m, src;
    double num;
    scanf("%d%d%d%lf", &n, &m, &src, &num);
    for(int i=0; i<m; i++)
    {
        int a, b;
        double rab, cab, rba, cba;
        scanf("%d%d%lf%lf%lf%lf", &a, &b, &rab, &cab, &rba, &cba);
        edge[i].u = a; edge[i].v = b;
        edge[i].r = rab; edge[i].c = cab;
        edge[i+m].u = b; edge[i+m].v = a;
        edge[i+m].r = rba; edge[i+m].c = cba;
    }
    if(Bellman_Ford(n, m*2, src, num))
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}