Arbitrage - poj 2240 (Bellman-ford)
2024-08-29 11:03:40
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 17374 | Accepted: 7312 |
Description
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.
Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
Input
The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".
Sample Input
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar 3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar 0
Sample Output
Case 1: Yes
Case 2: No
这题较简单,使用bellman-ford算法就可以了,注意输出,我因为输出WA几次
#include <iostream>
#include<map>
#include<string.h>
using namespace std;
struct edge{
int u,v;
float rate;
} e[*];
int cur_num,edge_num;
float dis[];
map<string,int> mp;
int Bellman_ford(int c){
memset(dis,,*sizeof(float));
dis[c]=1.0;
for(int i=;i<cur_num;i++){
for(int j=;j<edge_num;j++){
if(dis[e[j].v]<dis[e[j].u]*e[j].rate){
dis[e[j].v]=dis[e[j].u]*e[j].rate;
}
}
}
if(dis[c]>1.0)
return ;
else
return ;
}
int main() {
int count=;
cin>>cur_num;
while(cur_num){
mp.clear();
for(int i=;i<cur_num;i++){
string s;
cin>>s;
mp[s]=i;
}
cin>>edge_num;
for(int i=;i<edge_num;i++){
string s1,s2;
float rate;
cin>>s1>>rate>>s2;
e[i].u=mp[s1];
e[i].v=mp[s2];
e[i].rate=rate;
}
int flag=;
for(int i=;i<cur_num;i++){
flag=Bellman_ford(i);
if(flag)
break;
} if(flag)
cout<<"Case "<<++count<<": Yes"<<endl;
else
cout<<"Case "<<++count<<": No"<<endl;
cin>>cur_num;
}
return ;
}
最新文章
- 安全协议系列(五)---- IKE 与 IPSec(中)
- 21个免费的UI设计工具和资源网站,不管是web,js,android都
- JavaScript-hash数组for in 函数
- [转] Android获取Manifest中<;meta-data>;元素的值
- LZMA demo挑选使用备忘
- Shell如何传递字符串
- 说一说高级男装面料_SuMisura_新浪博客
- Win10系列:C#应用控件进阶7
- Datagrip导入导出为一个sql文件详细说明 (mysql)
- python基础-requests模块、异常处理、Django部署、内置函数、网络编程
- zookeeper 集群部署
- bzoj4556(sam)
- 菜鸟教程之工具使用(六)——让Maven项目直接在eclipse内部的Tomcat中运行
- C++ getline判断空行
- 软件工程结对作业01 psp表格
- JavaScript HTML DOM 入门详解
- 根据模板导出excel
- centos下设置自启动和配置环境变量的方法
- Sparsity Invariant CNNs
- echarts官网上的动态加载数据bug被我解决。咳咳/。
热门文章
- [BZOJ4568][SCOI2016]幸运数字(倍增LCA,点分治+线性基)
- Java Socket编程详细解说
- DOTween教程
- DotnetBrowser高级教程-(4)使用MVC框架5-使用视图
- Architecting Android…The clean way?
- ElasticSearch中设置排序Java
- 2017.4.19 慕课网-通过自动回复机器人学习mybatis
- perl学习笔记——输入与输出
- ASP.NET MVC生成安全验证码
- Visual Studio 2015 Update 1 安装到最后 KB3022398 错误解决方法