首页 > 代码库 > POJ 2240 - Arbitrage（最短路）
POJ 2240 - Arbitrage（最短路）
题意：
给出一些货币和货币之间的兑换比率，问是否可以使某种货币经过一些列兑换之后，货币值增加。
举例说就是1美元经过一些兑换之后，超过1美元。可以输出Yes，否则输出No。
分析：
首先我们要把货币之间的关系转化成一张图。转化时，用STL里面的map很方便。
为每种货币分配一个序列号，一个序列号代表了一个图中间的NODE，而node之间的edge用汇率表示。
一开始用Dijkstra算法做，死活AC不了，网友给的理由是：
由于Dijkstra算法不能处理带有负权值的最短路，但此题中，两种货币之间的兑换比率可能小于1，相当于这条路径的权值为负
前车之鉴，WA的代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<string.h> 5 #include<string> 6 #include<map> 7 using namespace std; 8 #define maxn 31 9 #define inf 0x3f3f3f3f10 double edges[maxn][maxn];11 double dist[maxn];12 typedef pair<int,int> P;13 void init(){14 for(int i=1;i<maxn;i++)15 for(int j=1;j<maxn;j++)16 edges[i][j]=(i==j?1:0);//1代表等价价换，0：代表无法交换17 }18 19 void dijkstra(int s,int n){20 bool visited[maxn];21 memset(visited,0,sizeof(visited));22 visited[s]=true;23 for(int i=1;i<=n;i++)24 dist[i]=edges[s][i];25 for(int i=1,u;i<=n;i++){26 double max=-1;27 for(int j=1;j<=n;j++)28 if(!visited[j]&&dist[j]>max){29 max=dist[j]; u=j;30 }31 32 visited[u]=true;33 for(int j=1;j<=n;j++){34 if(dist[u]*edges[u][j]>dist[j])35 dist[j]=dist[u]*edges[u][j];36 }37 }38 }39 40 int main(){41 //freopen("in.txt","r",stdin);42 int n,cases=0;43 while(scanf("%d",&n)!=EOF && n){44 cases++;45 init();46 map<string,int> ma;47 string s,t;48 for(int i=1;i<=n;i++){49 cin>>s;50 ma.insert(make_pair(s,i));51 }52 int m;53 double tmp;54 scanf("%d",&m);55 while(m--){56 cin>>s>>tmp>>t;57 edges[ma[s]][ma[t]]=tmp;58 }59 60 dijkstra(1,n);61 printf("Case %d: ",cases);62 if(dist[1]>1.0)63 printf("Yes\n");64 else 65 printf("No\n");66 }67 }
最后写了一个Floyd的代码版本，结果一下子就过了，我只能默默的哭了
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<string.h> 5 #include<string> 6 #include<map> 7 using namespace std; 8 #define maxn 31 9 #define inf 0x3f3f3f3f10 double edges[maxn][maxn];11 void init(){12 for(int i=1;i<maxn;i++)13 for(int j=1;j<maxn;j++)14 edges[i][j]=(i==j?1:0);//1：代表等价交换，0：代表无法交换15 }16 17 void floyd_warshall(int s,int n){18 for(int k=1;k<=n;k++){19 for(int i=1,u;i<=n;i++){20 for(int j=1;j<=n;j++){21 if(edges[i][k]*edges[k][j]>edges[i][j])//如果找到了更好的交换方案22 edges[i][j]=edges[i][k]*edges[k][j];23 }24 }25 }26 }27 28 int main(){29 //freopen("in.txt","r",stdin);30 int n,cases=0;31 while(scanf("%d",&n)!=EOF && n){32 cases++;33 init();34 map<string,int> ma;35 string s,t;36 for(int i=1;i<=n;i++){37 cin>>s;38 ma.insert(make_pair(s,i));39 }40 int m;41 double tmp;42 scanf("%d",&m);43 while(m--){44 cin>>s>>tmp>>t;45 edges[ma[s]][ma[t]]=tmp;46 }47 48 dijkstra(1,n);49 printf("Case %d: ",cases);50 /*for(int i=1,u;i<=n;i++){51 for(int j=1;j<=n;j++){52 printf("%.2f ",edges[i][j]);53 }54 printf("\n");55 }*/56 if(edges[1][1]>1.0)57 printf("Yes\n");58 else 59 printf("No\n");60 }61 }
【问题】：Folyd算法能处理包含负权边的图吗？
答案是可以的。Floyd-Warshall算法和Bellman-Ford算法一样，可以处理边是负数的情况。
---《挑战程序设计竞赛》 P.103
POJ 2240 - Arbitrage（最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。