转载请注明出处：http://acm.hdu.edu.cn/showproblem.php?pid=1217
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，则可以。否则不可以。
代码如下：
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<iostream>
using namespace std;
#define N 47
double M[N][N];
map<string,int>mm;
void init( int n)
{
for(int i = 1 ; i <= n ; i++ )
{
for(int j = 1 ; j <= n ;j++)
{
if(i == j)
M[i][j] = 1.0; //自身的汇率为1
else
M[i][j] = 0;
}
}
}
void floyd(int n)
{
for(int k = 1 ; k <= n ;k++)
{
for(int i = 1 ; i <= n ;i++ )
{
for( int j = 1 ; j <= n ;j++ )
{
if(M[i][j] < M[i][k] * M[k][j])
{
M[i][j] = M[i][k] * M[k][j];
}
}
}
}
}
int main()
{
char s1[147],s2[147],s[147];
int n, m,cnt = 0;
double gate;
while(~scanf("%d",&n) && n)
{
init(n);
for( int i = 1 ; i <= n ;i++)
{
scanf("%s",s);
mm[s] = i;
}
scanf("%d",&m);
for( int j = 1 ; j <= m ; j++)
{
scanf("%s%lf%s",s1,&gate,s2);
M[mm[s1]][mm[s2]] = gate;
}
floyd( n );
int flag = 0;
for( i = 1 ; i<= n ; i++)
{
if(M[i][i] > 1)
{
flag = 1;
break;
}
}
if( flag == 1)
{
printf("Case %d: Yes\n",++cnt);
continue;
}
printf("Case %d: No\n",++cnt);
}
return 0;
}
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
const int L = 35;
const double inf = 1000000;
map<string,int> mat;
int n,m;
char str[105],s1[105],s2[105];
double trip[35][35],dis[35];
int SPFA(int src)
{
queue<int> Q;
int vis[35],i;
int num[35];
for(i = 1; i<=n; i++)
vis[i] = dis[i] = num[i] = 0;
while(!Q.empty())
Q.pop();
dis[src] = 1.0;
vis[src] = 1;
Q.push(src);
while(!Q.empty())
{
int now = Q.front();
Q.pop();
vis[now] = 0;
for(i = 1; i<=n; i++)
{
if(dis[now]*trip[now][i]>dis[i])
{
dis[i] = dis[now]*trip[now][i];
if(dis[src]>1.0)
return 1;
if(!vis[i])
{
vis[i] = 1;
Q.push(i);
}
}
}
}
return 0;
}
int main()
{
int i,j,cas = 1;
double w;
while(~scanf("%d",&n),n)
{
mat.clear();
for(i = 1; i<=n; i++)
for(j = 1; j<=n; j++)
trip[i][j] = (i==j)?1.0:0;
for(i = 1; i<=n; i++)
{
scanf("%s",str);
mat[str] = i;
}
scanf("%d",&m);
while(m--)
{
scanf("%s%lf%s",s1,&w,s2);
trip[mat[s1]][mat[s2]] = w;
}
int flag = 0;
for(i = 1; i<=n; i++)
{
if(SPFA(i))
{
flag = 1;
break;
}
}
printf("Case %d: %s\n",cas++,flag?"Yes":"No");
}
return 0;
}
hdu 1217 Arbitrage Floyd||SPFA,布布扣,bubuko.com
hdu 1217 Arbitrage Floyd||SPFA
原文：http://blog.csdn.net/u012860063/article/details/25243475