poj 1860 Currency Exchange(最短路径的应用)
http://poj.org/problem?id=1860题意 ： 就是套汇的问题，汇率Rab， 增加了一个手续费Cab 。。。。。。。每次的结果是(本金 - 手续费) * 汇率，而且一个人拥有的钱的类型是已知的，拥有的value 钱的个数也是已知的， 问你能不能增值。
输入 ：
3 2 1 20.0 //钱种类个数汇率的个数，拥有第几种钱， 拥有多少钱
1 2 1.00 1.00 1.00 1.00 //钱a， 钱b， rab， cab， rba， cba
2 3 1.10 1.00 1.10 1.00
想法： 应用bellman-ford ：
应用bellman求解最短路径（上界松弛）和最长路径（下界松弛）的时候，都是松弛点 - 1次， 然后再看能否再进行松弛了。如果能，就证明有环。否则为最短或者最长路径（希望错了请大家指出）
当时看这个题的时候，被bellman求解最短路给束缚了， 即循环是点 - 1次， 但是这种最长路的正环不一定就在点 - 1 次松弛后，就能让目标点符合要求，也即是说不一定能松弛连接目标点的边，因为要看d与d[目标点(v)]的关系，也就是边，就像最短路得负环一样，他们是无限的增长下去的。
所以这个题 循环的终止条件有2个 ：
1。 当不能松弛的时候停止， 这样就代表这个图中没有正环，这样判断一下d是否大于value就可以了。
2。 发现d 〉value了，这种时候有可能是图有正环，也有可能图还没有松弛完毕，但是只要发现满足条件，就可以了。
对了，这个题还要注意精度
#include<stdio.h>
#define N 50000
#include<string.h>
#define max 999999
#define eps 1e-6
int n,m,x,vis,k;
double val,dis;//注意dis要用double
struct node
{
int u,v;
double r,c;
}p;
int bellman(int x)
{
int i,f;
memset(vis,0,sizeof(vis));
for(i=0;i<=n;i++)
{
dis=0;
}
dis=val;
while(dis<=val+eps)
{
f=0;
for(i=0;i<k;i++)
{
if(dis.v]+eps<(dis.u]-p.c)*p.r)
{
dis.v]=(dis.u]-p.c)*p.r;
f=1;
}
}
if(!f)return 0;//不能松弛啦
}
return 1;
}
int main()
{
int i,u,v;
double rvu,cvu,ruv,cuv;
while(scanf("%d%d%d%lf",&n,&m,&x,&val)!=EOF)
{
k=0;
for(i=0;i<m;i++)
{
scanf("%d%d%lf%lf%lf%lf",&u,&v,&ruv,&cuv,&rvu,&cvu);
p.u=u;
p.v=v;
p.r=ruv;
p.c=cuv;
k++;
p.u=v;
p.v=u;
p.r=rvu;
p.c=cvu;
k++;
}
int ans=bellman(x);
if(ans)printf("YES\n");
else printf("NO\n");
}
}
页:
[1]