链接:poj 1860

题意：给定n中货币。以及它们之间的税率。A货币转化为B货币的公式为 B=(V-Cab)*Rab,当中V为A的货币量，

求货币S通过若干此转换，再转换为原本的货币时是否会添加

分析：这个题就是推断是否存在正权回路。能够用bellman-ford算法，只是松弛条件相反

也能够用SPFA算法，推断经过转换后，转换为原本货币的值是否比原值大、、、

bellman-ford    0MS

#include<stdio.h>

#include<string.h>

struct stu

{

    int a,b;

    double r,c;

}edge[205];

double v,dis[105];

int s;

int bellmanford(int n,int m)

{

    int i,j,flag=0;

    memset(dis,0,sizeof(dis));

    dis[s]=v;

    for(i=1;i<=n-1;i++)

        for(j=1;j<=m;j++)

            if(dis[edge[j].a]&&(dis[edge[j].a]-edge[j].c)*edge[j].r>dis[edge[j].b])

                dis[edge[j].b]=(dis[edge[j].a]-edge[j].c)*edge[j].r;

    for(j=1;j<=m;j++)

        if(dis[edge[j].a]&&(dis[edge[j].a]-edge[j].c)*edge[j].r>dis[edge[j].b]){

            flag=1;

            break;

        }

    return flag;

}

int main()

{

    int i,j,l,r,n,m,flag;

    while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF){

        j=1;

        for(i=1;i<=m;i++){

            scanf("%d%d",&l,&r);

            scanf("%lf%lf",&edge[j].r,&edge[j].c);

            edge[j].a=l;

            edge[j].b=r;

            j++;

            edge[j].a=r;

            edge[j].b=l;

            scanf("%lf%lf",&edge[j].r,&edge[j].c);

            j++;

        }

        flag=bellmanford(n,2*m);

        if(flag)

            printf("YES\n");

        else

            printf("NO\n");

    }

    return 0;

}

SPFA+邻接表  16MS

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

struct stu

{

    int a,b;

    double r,c;

}edge[205];

double v,dis[105];

int s,first[205],next[205],vis[105];

int SPFA(int n,int m)

{

    int i,pos;

    queue<int> q;

    memset(dis,0,sizeof(dis));

    memset(vis,0,sizeof(vis));

    dis[s]=v;

    q.push(s);

    vis[s]=1;

    while(!q.empty()){

        pos=q.front();

        q.pop();

        vis[pos]=0;

        i=first[pos];

        while(i!=-1){

            if((dis[pos]-edge[i].c)*edge[i].r>dis[edge[i].b]){

                dis[edge[i].b]=(dis[pos]-edge[i].c)*edge[i].r;

                if(!vis[edge[i].b]){

                    q.push(edge[i].b);

                    vis[edge[i].b]=1;

                }

            }

            i=next[i];

        }

        if(dis[s]>v)

            return 1;

    }

    return 0;

}

int main()

{

    int i,j,l,r,n,m,flag;

    while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF){

        j=1;

        for(i=1;i<=m;i++){

            scanf("%d%d",&l,&r);

            scanf("%lf%lf",&edge[j].r,&edge[j].c);

            edge[j].a=l;

            edge[j].b=r;

            j++;

            edge[j].a=r;

            edge[j].b=l;

            scanf("%lf%lf",&edge[j].r,&edge[j].c);

            j++;

        }

        memset(first,-1,sizeof(first));

        for(i=1;i<=2*m;i++){

            next[i]=first[edge[i].a];

            first[edge[i].a]=i;

        }

        flag=SPFA(n,2*m);

        if(flag)

            printf("YES\n");

        else

            printf("NO\n");

    }

    return 0;

}