pku1860 Currency Exchange

#include<stdio.h>

const int MAX=105;
const double EXP=1e-8;
double dis[MAX];
struct Edge
{
    int v1,v2;
    double c,r;
};
Edge edge[MAX*2];
int m,n,s;
double v;

bool bellman_ford()
{
    for(int i=1;i<=n;i++) dis[i]=0;
    dis[s]=v;
    while(dis[s]<=v)
    {
        bool relax=0;
        for(int i=0;i<m;i++)
            if(dis[edge[i].v2]<(dis[edge[i].v1]-edge[i].c)*edge[i].r)
            {
                relax=1;
                dis[edge[i].v2]=(dis[edge[i].v1]-edge[i].c)*edge[i].r;
            }

        if(!relax) return false;
    }
    return true;
}

int main()
{
    while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF)
    {
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%lf%lf%lf%lf",&edge[i*2].v1,&edge[i*2].v2,&edge[i*2].r,&edge[i*2].c,&edge[i*2+1].r,&edge[i*2+1].c);
            edge[i*2+1].v1=edge[i*2].v2;edge[i*2+1].v2=edge[i*2].v1;
        }

        m*=2;
        if(bellman_ford()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

总结：

可以在两点间循环往复兑换从而可以使钱不断增加，也就是图中存在局部回路，可以采用Bellman-Fold算法进行松弛，逐步增大源点s到点v的最短路的估算值。