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
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#define INF 100000000
#define MAX 40
using namespace std ;
double dis[MAX],graph[MAX][MAX];
bool Bellman_Ford(int n)
{
for(int i = 0 ; i <= n ; ++i)
{
dis[i] = 0.0;
}
dis[0] = 1 ;
for(int i = 0 ; i < n-1 ; ++i)
{
for(int j = 0 ; j < n ; ++j)
{
for(int k = 0 ; k < n ; ++k)
{
if(graph[k][j] > 0.000001)
{
if(dis[j] < dis[k]*graph[k][j])
{
dis[j] = dis[k]*graph[k][j] ;
}
}
}
}
}
for(int i = 0 ; i < n ; ++i)
{
for(int j = 0 ; j < n ; ++j)
{
if(dis[i] < dis[j]*graph[j][i]) //只要有一个存在即可。
{
return true ;
}
}
}
return false ;
}
int main()
{
int n , m , c = 1 ;
double rate ;
map<string,int> search;
string nameA,nameB,temp ;
while(cin>>n && n)
{
for(int i = 0 ; i < n ; ++i)
{
cin>>temp ;
search.insert(pair<string,int>(temp,i));
}
cin>>m;
memset(graph,0,sizeof(graph)) ;
for(int j = 0 ; j < m ; ++j)
{
cin>>nameA>>rate>>nameB;
int x = search[nameA] , y = search[nameB] ;
graph[x][y] = rate ;
}
if(Bellman_Ford(n))
{
printf("Case %d: Yes\n",c++);
}
else
{
printf("Case %d: No\n",c++);
}
search.clear() ;
}
return 0 ;
}<pre name="code" class="cpp">#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#define INF 100000000
#define MAX 40
using namespace std ;
double graph[MAX][MAX];
bool Floyd(int n)
{
for(int k = 0 ; k < n ; ++k)
{
for(int i = 0 ; i < n ; ++i)
{
for(int j = 0 ; j < n ; ++j)
{
if(graph[i][j] < graph[i][k]*graph[k][j])
graph[i][j] = graph[i][k]*graph[k][j] ;
}
}
}
for(int i = 0 ; i < n ; ++i)
{
if(graph[i][i]>1)
{
return true ;
}
}
return false ;
}
int main()
{
int n , m , c = 1 ;
double rate ;
map<string,int> search;
string nameA,nameB,temp ;
while(cin>>n && n)
{
memset(graph,0,sizeof(graph)) ;
for(int i = 0 ; i < n ; ++i)
{
cin>>temp ;
search.insert(pair<string,int>(temp,i));
graph[i][i] = 1 ;
}
cin>>m;
for(int j = 0 ; j < m ; ++j)
{
cin>>nameA>>rate>>nameB;
int x = search[nameA] , y = search[nameB] ;
graph[x][y] = rate ;
}
if(Floyd(n))
{
printf("Case %d: Yes\n",c++);
}
else
{
printf("Case %d: No\n",c++);
}
search.clear() ;
}
return 0 ;
}hdu 1217 Arbitrage 两种算法AC代码，Floyd+Bellman-Ford 大水题一枚 注意是有向图~~
原文：http://blog.csdn.net/lionel_d/article/details/43868421