http://acm.hdu.edu.cn/showproblem.php?pid=1217
题意:给出各种钱之间的兑换机制,求不断兑换后是否可以产生利润?
对于第一个案例:start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent
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
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define L long long
#define inf 0x3fffffff
#define M 1005
map<string, int> m; //映射
double mon[35][35];
int main()
{
double x;
int n, i, k, j, cc = 1;
string s, p;
while (cin >> n, n)
{
for (i = 0; i < n; i++)
{
cin >> s;
m[s] = i; //把string映射为[0,n-1]的编号
}
cin >> k;
memset (mon, 0, sizeof(mon)); //初始化
while (k--)
{
cin >> s >> x >> p;
mon[m[s]][m[p]] = x; //从s号变为p号要乘以x
}
/*****************floyd神器*****************/
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
for (k = 0; k < n; k++) //floyd-构造所有情况的神器
if (mon[j][k] < mon[j][i] * mon[i][k])
//就像路径,从j到k可以由j到i再到k
mon[j][k] = mon[j][i] * mon[i][k]; //更新,所谓的松弛技术
/*****************floyd神器*****************/
for (i = 0; i < n; i++)
if (mon[i][i] > 1.0) //经过变换后>1.0说明获得利润
break;
printf ("Case %d: ", cc++);
if (i < n)
puts ("Yes");
else puts ("No");
}
return 0;
}
分享到:
相关推荐
北大POJ2240-Arbitrage【Floyd】 解题报告+AC代码
中国数学建模-数学工具-Floyd最短路算法的MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss......
基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
利用误差扩散算法中的Floyd-Steinberg抖动算法来对图像进行二值化处理,从而方便图像调频加网输出Floyd-Steinberg
Floyd算法 详细介绍了Floyd算法的应用
最短路径算法 floyd
本代码是floyd算法的通用matlab程序,代码写的十分经典,是数模比赛的利器
使用c++,调用mpi进行floyd并向计算
floyd算法m文件
使用Floyd算法,求解点对之间的最短距离。图结构使用邻接矩阵存储。
matlab实现的floyd算法,matlab实现的floyd算法
floyd算法,C语言编写的程序,适合学生作业。非常专业
更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd...
Floyd算法.doc
floyd最短路算法 最短路程序
floyd 源代码 matlab floyd算法的matlab源代码实现
Floyd算法是经典的最短路径算法之一,应用广泛,可以求解多对多和一对一的最短路;
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd