poj 1860 Currency Exchange(bellmax_ford)

解题思路

题意：

       要通过套汇把钱增值，通过一个货币兑换点的时候要付一定的手续费再乘上汇率才是实际得到的钱。问能不能通过几次兑换，能使自己本来的钱增加。

 

思路：

       要实现套汇，有两种情况:

一种是有正权环，即有n个点组成的环（不包含原货币点），每过环的一条边都能使钱增值，只要你无限多次在这个环里兑换，你的钱就能无限增值，当然前提是他条件不变（这比较爽~）。

另一种是没有那种环，但是你兑换回原货币时比原来多了，其实这就相当于一个包含原货币点的正环。总之就是求有没有正权环的问题。

跟bellman_ford求负权环类似，所以是它的一个变形。改变的是松弛部分，结果要能比原来大才松弛。

源程序

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 10 //102

#define eps 1e-8
double r[N][N], c[N][N];
double v, dis[N];
int n;

int bellman_ford(int s, double v)
{
    int i, j, k, mark;
    dis[s] = v;
     for(i=1; i<=n-1; i++)
    {
        mark = 0;
        for(j=1; j<=n; j++)
        {
            for(k=1; k<=n; k++)
            {
                if(dis[k] +eps< (dis[j] - c[j][k]) * r[j][k]) //改变的松弛操作
                {
                    dis[k] = (dis[j] - c[j][k]) * r[j][k];
                    mark = 1;
                }
            }
        }
        if(!mark)
            break;
    }

    for(j=1; j<=n; j++)
        {
            for(k=1; k<=n; k++)
            {
                if(dis[k] +eps < (dis[j] - c[j][k]) * r[j][k])
                {
                    dis[k] = (dis[j] - c[j][k]) * r[j][k];
                    v = dis[s];
                    return 1;
                }
            }
        }
    v = dis[s];
    return 0;
}

int main()
{
    int i, j;
    int m, s;
    int a, b;
    double r1, r2, c1, c2, vv;

    freopen("in.txt", "r", stdin);
    scanf("%d%d%d%lf", &n, &m, &s, &v);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%lf%lf%lf%lf", &a, &b, &r1, &c1, &r2, &c2);
        r[a][b] = r1;
        c[a][b] = c1;
        r[b][a] = r2;
        c[b][a] = c2;
    }
    vv = v;
    if(bellman_ford(s, v)) //有正权环
        printf("YES\n");
    else if(v - vv > eps) //没有正权环，钱增值了
        printf("YES\n");
    else printf("NO\n"); //不能实现套汇

    getch();
    return 0;
}
memory : 336k

time: 0MS