题目：
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
Case 1: Yes Case 2: No
题目分析：
使用floyd来求最长路。这道题需要注意以下的一些地方。
1）文字索引需要转化成数字索引。因为数组里面是数字索引。
string huobi_name;
int i;
for(i = 0 ; i < n ; ++i){//***将文字索引转换成数字索引.因为数组中用的是数字索引
cin >> huobi_name;
money[huobi_name] = huobi_type++;
}
2）求最长路时的floyd的初始化方法的写法。
/**
* 这道题中floyd的初始化.
* 以前的写法如上提所示.
* 这里讲一下区别。以前是求最短路径,是一个由大到小的紧缩过程。
* 而这道题抽象以下其实是求最长路径,是一个由小到大的放大的过程
*/
void initial() {
int i, j;
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
e[i][j] = 0;//所有东西一开始都初始化位0
}
}
}3）求最长路时floyd函数的放缩的写法。其实就是把 > 换成 < 即可。
/**
*floyd算法
*/
void floyd() {
int i, j, k;
for (k = 1; k <= n; ++k) {//遍历所有的中间点
for (i = 1; i <= n; ++i) {//遍历所有的起点
for (j = 1; j <= n; ++j) {//遍历所有的终点
//*****floyd求最长路的写法
if (e[i][j] < e[i][k] * e[k][j]) {//如果当前i-->j的距离 小于 i-->k--->j的距离之和
e[i][j] = e[i][k] * e[k][j];//更新从i--->j的最短路径
}
}
}
}
}这道题的代码如下：
/*
* hdu1217.cpp
*
* Created on: 2015年3月27日
* Author: Administrator
*/
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxn = 31;
double e[maxn][maxn];
int n;
const int inf = 99999999;
/*
* void initial() {
int i, j;
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
if (i == j) {
e[i][j] = 0;
} else {
e[i][j] = inf;
}
}
}
}
*
*/
/**
* 这道题中floyd的初始化.
* 以前的写法如上提所示.
* 这里讲一下区别。以前是求最短路径,是一个由大到小的紧缩过程。
* 而这道题抽象以下其实是求最长路径,是一个由小到大的放大的过程
*/
void initial() {
int i, j;
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
e[i][j] = 0;//所有东西一开始都初始化位0
}
}
}
/**
*floyd算法
*/
void floyd() {
int i, j, k;
for (k = 1; k <= n; ++k) {//遍历所有的中间点
for (i = 1; i <= n; ++i) {//遍历所有的起点
for (j = 1; j <= n; ++j) {//遍历所有的终点
//*****floyd求最长路的写法
if (e[i][j] < e[i][k] * e[k][j]) {//如果当前i-->j的距离 小于 i-->k--->j的距离之和
e[i][j] = e[i][k] * e[k][j];//更新从i--->j的最短路径
}
}
}
}
}
int main(){
int cnt = 1;
while(scanf("%d",&n)!=EOF,n){
map<string,int> money;
int huobi_type = 1;
string huobi_name;
int i;
for(i = 0 ; i < n ; ++i){//***将文字索引转换成数字索引.因为数组中用的是数字索引
cin >> huobi_name;
money[huobi_name] = huobi_type++;
}
initial();
int m;
scanf("%d",&m);
while(m--){
string from;
string to;
double change;
cin >> from >> change >> to;
e[money[from]][money[to]] = change;
}
floyd();
bool flag = false;
for(i = 1 ; i <= n ; ++i){//遍历所有的货币
if(e[i][i] > 1){//看是否存在一种货币经过一个兑换回路以后 >= 1个单元
//如果存在
flag = true;//则将flag标记为true。
break;//跳出循环
}
}
//输出最后的结果
if(flag == true){
printf("Case %d: Yes\n",cnt++);
}else{
printf("Case %d: No\n",cnt++);
}
}
return 0;
}
(floyd 1.1)hdu 1217 Arbitrage(使用floyd来求最长路——判断是否存在一种货币，经过一个兑换回路以后>=1单元)
原文：http://blog.csdn.net/hjd_love_zzt/article/details/44674157