这道题分类在最短路径里面，求的却不是最短，而是最大；运用的是最短路径的相反的思想；
原来算法思想只是一种解决某种问题的思路，并不是固定不变的，要想使用一组一种思想解决相关的问题，必须要领会贯通才行
*********************************************************************************************
*******************************************************************************************
#include<iostream>#include<map>#include<string>using namespace std;
#define DEBUG 1const int MaxSize=31;double Map[MaxSize][MaxSize],G[MaxSize][MaxSize];int num;
void init(){ int i,j; for(i=1;i<=num;i++){ for(j=i;j<=num;j++){ Map[i][j]=Map[j][i]=0; } Map[i][i]=1; } }
void Floyd(){ int i,j,k; for(i=1;i<=num;i++) for(j=1;j<=num;j++) G[i][j]=Map[i][j]; for(k=1;k<=num;k++){ for(i=1;i<=num;i++){ for(j=1;j<=num;j++){ if(G[i][k]>0&&G[k][j]>0&&G[i][j]<G[i][k]*G[k][j]) G[i][j]=G[i][k]*G[k][j]; } } }} int main(){ #if DEBUG freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin); freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout); #endif int i,j,k,n,cases=1; double rr; string str,str1,str2; while(cin>>num){ if(num==0)break; init(); map<string,int> m; for(i=1;i<=num;i++){ cin>>str; m.insert(make_pair(str,i));} cin>>n; for(i=0;i<n;i++){ cin>>str1>>rr>>str2; map<string,int>::iterator it1=m.find(str1); map<string,int>::iterator it2=m.find(str2); Map[it1->second][it2->second]=rr; } Floyd(); for(i=1;i<=num;i++){ if(G[i][i]>1)break;} if(i<=num)cout<<"Case "<<cases<<": Yes"<<endl; else cout<<"Case "<<cases<<": No"<<endl; cases++; getchar(); } return 0;}
转载于:https://www.cnblogs.com/miaycl/archive/2010/07/28/1786703.html
相关资源：JAVA上百实例源码以及开源项目