POJ 1860 - Currency Exchange

Description

Input

Output

Sample Input

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

Sample Output

YES

Source

解释一下基本题意，SB—hypo有s货币，价值为V，他想获得很多其它的货币。身为一个妻管严，该怎么办？╮(╯▽╰)╭，无奈。。。货币交换公式 (B货币)  = （A货币总量-佣金）*汇率。

输入N,M,S,V;

以下M行，line 1 代表货币1 到 货币2 的 汇率、佣金，货币2 到 货币1 的 汇率、佣金

line 2 代表货币2 到 货币3 的 汇率、佣金，货币3 到 货币2 的 汇率、佣金

打印SB-hypo是否能添加收入？YES/NO

PS:  没什么难度。就是贝尔曼的模板，敲上就差点儿相同A了，可是WA了两次，以为是精度的问题，可是看了一下DISCUSS之后，发现dis[]的初始化不正确，应该为0，而不INF。由于这个题是逆向使用贝尔曼算法，找的不是负环。且没有负环。并代表就有正欢，仅仅能说明可能存在最短路，而是能够使之钱数无限添加的正环。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
const int INF = 1<<20;
const int N = 110;
const int Size = 9999;
using namespace std;
double mapp[N][N];
double dis[N],ANS;
int n,m,s,l;
double num;
struct node{
    int u,v;
    double hui,yong;
}edge[Size];
void init()
{
    l = 0;//若是找负环，dis[]应该初始化INF
    for(int i = 0;i<N;i++) //这里须要注意。由于找的是正环，初始化应该为0，可是不明确为什么不能为负
        dis[i] = 0;
}
int Bellamn()
{
    int flag = 0;
    for(int i = 0;i<n;i++)
    {
        flag = 0;
        for(int j = 0;j<l;j++)
        {     //曾经是 dis[edge[j].v] > dis[edge[j].u] + edge[j].w; 更新最短路 
            if(dis[edge[j].v] < (dis[edge[j].u] - edge[j].yong)* edge[j].hui) // 更新相对最长路
                {
                    dis[edge[j].v] = (dis[edge[j].u] - edge[j].yong)* edge[j].hui;
                    flag = 1;
                }
        }
        if(flag==0)//更新完成跳出
            break;
    }
    for(int j = 0;j<l;j++)
        {
            if(dis[edge[j].v] < (dis[edge[j].u] - edge[j].yong)* edge[j].hui)//推断正环
                {
                   return 1;
                }
        }
        return 0;
}
int main()
{
    int a,b;
    double c,d,cc,dd;
    while(~scanf("%d%d%d%lf",&n,&m,&s,&num))
    {
        init();
        dis[s] = num;
        for(int i = 0;i<m;i++)
        {
            scanf("%d%d%lf%lf%lf%lf",&a,&b,&c,&d,&cc,&dd);
            edge[l].u = a; edge[l].v = b; edge[l].hui = c; edge[l++].yong = d;
            edge[l].u = b; edge[l].v = a; edge[l].hui = cc; edge[l++].yong = dd;
        }
        int st = Bellamn();
        (st==1)?puts("YES"):puts("NO");
    }
    return 0;
}