poj 1860 Currency Exchange (bellman-ford 判断正环)

cxg518

　　http://poj.org/problem?id=1860
　　
　　题意： 有n种货币 m个交换点 初始为s货币 并由v的面额
　　每个交换点可以互换两种货币 汇率为r 但是需要c的手续费 而且a换b与 b换a 的汇率和手续费不相同
　　问nick能否通过交换使货币金额数增加
　　
　　思路： 存在正环的情况下 金额数能不断增长
　　先通过bellman-ford 求出最长路
　　在判断是否存在 继续满足 (d[x]-c)*r>d[y] 的边
　　如果存在 则说明存在正环
　　





#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;
int u[300],v[300];
double r[300],c[300];
double d[300];
int main()
{
int n,m,s;
double vv;
int i,j,k;
int a,b;
double r1,c1,r2,c2;
while(scanf("%d%d%d%lf",&n,&m,&s,&vv)!=EOF)
{
for(i=1;i<=m*2;i+=2)
{
scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
u=a;  v=b;  r=r1;  c=c1;
u[i+1]=b;v[i+1]=a;r[i+1]=r2;c[i+1]=c2;
}
memset(d,0,sizeof(d));
d=vv;
int ok=0;
for(k=0;k<n-1;k++)
{
for(i=1;i<=m*2;i++)
{
int x=u,y=v;
if((d[x]-c)*r>d[y])
{
d[y]=(d[x]-c)*r;
}
}
}
for(i=1;i<=m*2;i++)
{
if(ok) break;
int x=u,y=v;
if((d[x]-c)*r>d[y])
{
ok=1;
}
}
if(ok) printf("YES\n");
else printf("NO\n");
}
return 0;
}
View Code