POJ-1860 解题报告

题意简述

某城市有M(1<=M<=100)个货币兑换站,可以兑换N(1<=N<=100)种货币,每个兑换站只能互换两种货币,且汇率与手续费各不相同。某人初始时手中有V元货币S,问他是否有可能通过货币兑换,在最后换回货币S时实现盈利,有可能则输出YES,否则输出NO。

算法分析

本题可抽象为一张有N个节点的有向图,一个兑换站就是它所兑换的两种货币间的两条有向边。边的权值有两个:汇率及手续费。

问题可化简为:从定点出发找正权环。由于可以通过无限次走正权环使得收益趋于无穷,所以不考虑返程开销。

容易发现,这是Bellman-Ford算法的逆用。将求最短路改为求最长路,再找可以无限松弛的正环,即可得解。

只要将Bellman-Ford稍微改进。初始时所有节点不再赋为无穷大,而是改为无穷小(0)。比较时,注意权值计算式的变化即可。详见程序样例。

具体的Bellman-Ford及最短路各算法另开文。

Problem Status: AC。时间32ms,内存184k

程序样例

[c]
#include<stdio.h>

struct edge{
int a;
int b;
double r;
double c;
};

int bellman_ford(double d[],struct edge x[],int n,int m,int s,double v)
{
int i,j,flag;
d[s]=v;
for(i=1;i<=n-1;i++)
{
flag=0;
for(j=0;j<2*m;j++)
{
if(d[x[j].b]<(d[x[j].a]-x[j].c)*x[j].r)
{
d[x[j].b]=(d[x[j].a]-x[j].c)*x[j].r;
flag=1;
}
}
if(!flag) break;
}
for(j=0;j<2*m;j++)
{
if(d[x[j].b]<(d[x[j].a]-x[j].c)*x[j].r) return 1;
}
return 0;
}

int main()
{
int n,m,s,i,t=0;
struct edge x[202];
double v,d[101]={0};
scanf("%d%d%d%lf",&n,&m,&s,&v);
for(i=0;i<m;i++)
{
scanf("%d%d%lf%lf",
&x[t].a,&x[t].b,&x[t].r,&x[t].c);
t++;
x[t].a=x[t-1].b;
x[t].b=x[t-1].a;
scanf("%lf%lf",&x[t].r,&x[t].c);
t++;
}
if(bellman_ford(d,x,n,m,s,v)) printf("YESn");
else printf("NOn");
return 0;
}
[/c]

One thought on “POJ-1860 解题报告

Leave a Reply

Your email address will not be published. Required fields are marked *