poj 1860 (Bellman_Ford判断正环)

题意：给出n种货币，m中交换关系，给出两种货币汇率和手续费，求能不能通过货币间的兑换使财富增加。

用Bellman_Ford 求出是否有正环，如果有的话就可以无限水松弛，财富可以无限增加。


#include<string.h>  
#include<stdio.h>  
const int N=110;  
const int inf=0x3fffffff;  
int start,num,n;  
double dist[N],wf;  
struct edge  
{  
    int st,ed;  
    double cost,w;  
}e[220];  
void addedge(int x,int y,double w,double c)  
{  
    e[num].st=x;e[num].ed=y;e[num].cost=c;e[num++].w=w;  
}  
int Bellman_Ford()  
{  
    int flag=0,i,u,v,j;  
    for(i=1;i<=n;i++)  
        dist[i]=0;  
    dist[start]=wf;  
    for(i=1;i<n;i++)//n-1次松弛  
    {  
        for(j=0;j<num;j++)  
        {  
            u=e[j].st;v=e[j].ed;  
            if(dist[v]<(dist[u]-e[j].cost)*e[j].w)  
            {  
                dist[v]=(dist[u]-e[j].cost)*e[j].w;  
                flag=1;  
            }  
        }  
        if(flag==0)break;  
    }  
    for(i=0;i<num;i++)  
        if(dist[e[i].ed]<(dist[e[i].st]-e[i].cost)*e[i].w)//有正环  
            return 1;  
    return 0;  
}  
int main()  
{  
    int m,i,x,y;  
    double a,b,c,d;  
    while(scanf("%d%d%d%lf",&n,&m,&start,&wf)!=-1)  
    {  
        num=0;  
        for(i=1;i<=m;i++)  
        {  
            scanf("%d%d%lf%lf%lf%lf",&x,&y,&a,&b,&c,&d);  
            addedge(x,y,a,b);  
            addedge(y,x,c,d);  
        }  
        if(Bellman_Ford())  
            printf("YES\n");  
        else printf("NO\n");  
    }  
    return 0;  
}

补充：移动开发 , IOS ,