POJ 1860 Currency Exchange

Description

n个点m个关于路的叙述

起点start 初始钱币ini

此 彼 此->彼汇率 手续费 彼到此汇率 手续费

The link of this problem http://poj.org/problem?id=1860

最短路变形

“最远路”

Bellman-Ford 判 正权环

Code of Bellman-Ford

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 105;///点的上界
const int inf = 0x3f3f3f3f;

int cnt;///边的计数
struct edge///Bellman-Ford 算法暴力遍历双向边,无pre
{
    int from, to;
    double w, cost;
} a[N << 1]; ///等同于邻接矩阵了

int n, m;///n为点的个数（注意编号是0 ~ n - 1还是1 ~ n），m为双向边的描述
double dis[N];///起点到某点的等效最短路(抄模板时顺手写了int)
double ini;

void add(int from, int to, double w, double cost)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].cost = cost;
    cnt++;
}

bool Bellman_Ford(int start)
{
    memset(dis, 0, sizeof(dis));
    dis[start] = ini;///自己换自己 1 : 1
    int tot = n - 1;
    while(tot--)///n个点，n次松弛
    {
        bool flag = 0;///优化
        for(int i = 0; i < cnt; ++i)///对所有边
            if(dis[ a[i].to ] < (dis[ a[i].from ] - a[i].cost) * a[i].w)
            {
                flag = 1;
                dis[ a[i].to ] = (dis[ a[i].from ] - a[i].cost) * a[i].w;
            }
        if(!flag)
            break;
    }
    for(int i = 0; i < cnt; ++i)
        if(dis[ a[i].to ] < (dis[ a[i].from ] - a[i].cost) * a[i].w)
            return 1;///有正权环
    return 0;
}

int main()
{
    int start;
//    while(~scanf("%d%d%d%lf", &n, &m, &start, &ini))
    while(cin >> n >> m >> start >> ini)
    {
        cnt = 0;
        int b, c;
        double d, e, f, g;
        for(int i = 0; i < m; ++i)
        {
//            scanf("%d%d%lf%lf%lf%lf", &b, &c, &d, &e, &f, &g);
            cin >> b >> c >> d >> e >> f >> g;
            add(b, c, d, e);
            add(c, b, f, g);///Debug一小时最后发现错把b写成d!!!!!!!!
        }
        if(Bellman_Ford(start))
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    return 0;
}