poj 1860 Currency Exchange (bellman-ford 判断正环)
http://poj.org/problem?id=1860题意： 有n种货币 m个交换点 初始为s货币 并由v的面额
每个交换点可以互换两种货币 汇率为r 但是需要c的手续费 而且a换b与 b换a 的汇率和手续费不相同
问nick能否通过交换使货币金额数增加
思路： 存在正环的情况下 金额数能不断增长
先通过bellman-ford 求出最长路
在判断是否存在 继续满足 (d-c)*r>d 的边
如果存在 则说明存在正环
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;
int u,v;
double r,c;
double d;
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=b;v=a;r=r2;c=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-c)*r>d)
{
d=(d-c)*r;
}
}
}
for(i=1;i<=m*2;i++)
{
if(ok) break;
int x=u,y=v;
if((d-c)*r>d)
{
ok=1;
}
}
if(ok) printf("YES\n");
else printf("NO\n");
}
return 0;
}
View Code
页:
[1]