POJ1860-Currency Exchange

来源:互联网 时间:1970-01-01

转载请注明出处:優YoU  http://user.qzone.qq.com/289065406/blog/1299337940

 

提示:关键在于反向利用Bellman-Ford算法

题目大意

有多种汇币,汇币之间可以交换,这需要手续费,当你用100A币交换B币时,A到B的汇率是29.75,手续费是0.39,那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加

货币的交换是可以重复多次的,所以我们需要找出是否存在正权回路,且最后得到的s金额是增加的

怎么找正权回路呢?(正权回路:在这一回路上,顶点的权值能不断增加即能一直进行松弛)

 

 

题目分析:

一种货币就是图上的一个点

一个“兑换点”就是图上两种货币之间的一个兑换环,相当于“兑换方式”M的个数,是双边

唯一值得注意的是权值,当拥有货币A的数量为V时,A到A的权值为K,即没有兑换

而A到B的权值为(V-Cab)*Rab

本题是“求最大路径”,之所以被归类为“求最小路径”是因为本题题恰恰与bellman-Ford算法的松弛条件相反,求的是能无限松弛的最大正权路径,但是依然能够利用bellman-Ford的思想去解题。

因此初始化d(S)=V   而源点到其他店的距离(权值)初始化为无穷小(0),当s到其他某点的距离能不断变大时,说明存在最大路径

 

 1 //Memory Time 
2 //252K 16MS
3
4 #include<iostream>
5 using namespace std;
6
7 int n; //货币种数
8 int m; //兑换点数量
9 int s; //持有第s种货币
10 double v; //持有的s货币的本金
11
12 int all; //边总数
13 double dis[101]; //s到各点的权值
14
15 class exchange_points
16 {
17 public:
18 int a; //货币a
19 int b; //货币b
20 double r; //rate
21 double c; //手续费
22 }exc[202];
23
24 bool bellman(void)
25 {
26 memset(dis,0,sizeof(dis)); //这里与bellman的目的刚好相反。初始化为源点到各点距离无穷小
27 dis[s]=v; //即bellman本用于找负环,求最小路径,本题是利用同样的思想找正环,求最大路径
28
29 /*relax*/
30
31 bool flag;
32 for(int i=1;i<=n-1;i++)
33 {
34 flag=false;
35 for(int j=0;j<all;j++)
36 if(dis[exc[j].b] < (dis[exc[j].a] - exc[j].c) * exc[j].r) //寻找最长路径
37 { //进行比较的是"某点到自身的权值"和"某点到另一点的权值"
38 dis[exc[j].b] = (dis[exc[j].a] - exc[j].c) * exc[j].r;
39 flag=true;
40 }
41 if(!flag)
42 break;
43 }
44
45 /*Search Positive Circle*/
46
47 for(int k=0;k<all;k++)
48 if(dis[exc[k].b] < (dis[exc[k].a] - exc[k].c) * exc[k].r) //正环能够无限松弛
49 return true;
50
51 return false;
52 }
53
54 int main(void)
55 {
56 int a,b;
57 double rab,cab,rba,cba; //临时变量
58
59 while(cin>>n>>m>>s>>v)
60 {
61 all=0; //注意初始化
62 for(int i=0;i<m;i++)
63 {
64 cin>>a>>b>>rab>>cab>>rba>>cba;
65 exc[all].a=a;
66 exc[all].b=b;
67 exc[all].r=rab;
68 exc[all++].c=cab;
69 exc[all].a=b;
70 exc[all].b=a;
71 exc[all].r=rba;
72 exc[all++].c=cba;
73 }
74
75 /*Bellman-form Algorithm*/
76
77 if(bellman())
78 cout<<"YES"<<endl;
79 else
80 cout<<"NO"<<endl;
81 }
82
83 return 0;
84 }
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b我的新浪微博:http://weibo.com/lyy289065406我的腾讯微博:http://t.qq.com/liao5422我的QQ空间:http://user.qzone.qq.com/289065406我的百度空间:http://hi.baidu.com/you289065406/home我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


相关阅读:
Top