http://acm.hdu.edu.cn/showproblem.php?pid=1217这次是求最大汇率，不过不是加，是乘法。用floyd算法。
#include <iostream>
#include <string>
using namespace std;
const int M=31;
string data[M];
double map[M][M];
//double dis[M][M];
//bool visit[M];
int n,m;
/**//*void dj(int i)
{
int j,temp,k;
double max;
memset(visit,0,sizeof(visit));
visit[i]=true;
for(j=1;j<=n;j++)
dis[i][j]=map[i][j];
dis[i][i]=1;
for(j=1;j<n;j++)
{
max=-1;
for(k=1;k<=n;k++)
if(!visit[k] && dis[i][k]>max)
{
max=dis[i][k];
temp=k;
}
visit[temp]=true;
for(k=1;k<=n;k++)
if(!visit[k] && dis[i][k]<dis[i][temp]*map[temp][k])
dis[i][k]=dis[i][temp]*map[temp][k];
}
}*/
void floyd()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(map[i][j]<map[i][k]*map[k][j])
map[i][j]=map[i][k]*map[k][j];
}
int main()
{
int i,pi,pj,t=1,j;
double price;
string a,b;
bool flag;
while(cin>>n,n)
{
flag=false;
memset(map,0,sizeof(map));
for(i=1;i<=n;i++)
cin>>data[i];
cin>>m;
while(m--)
{
cin>>a>>price>>b;
pi=pj=0;
for(i=1;i<=n;i++)
{
if(data[i]==a)
pi=i;
if(data[i]==b)
pj=i;
if(pi && pj)
break;
}
map[pi][pj]=price;
}
/**//*
for(i=1;i<=n;i++)
dj(i);
for(i=1;i<=n && flag==false;i++)
for(j=1;j<=n;j++)
if(dis[i][j]*dis[j][i]>1)
{
cout<<dis[i][j]*dis[j][i]-1<<endl;
flag=true;
break;
}
*/
floyd();
for(i=1;i<=n;i++)
if(map[i][i]>1)
{
flag=true;
break;
}
if(flag)
cout<<"Case "<<t++<<": Yes\n";
else
cout<<"Case "<<t++<<": No\n";
}
return 0;
}上面注释的是我写的迪杰斯特拉算法，为什么是错的呢？以前也是这么写的，烦。。。。
posted on 2011-09-15 19:07
大大木马 阅读(351)
评论(0) 编辑 收藏 引用