(51)-POJ 2263 Heavy Cargo算法设计与分析

POJ2263HeavyCargo(Floyd变形)\t"/u013480600/article/details/_blank"focus_best

2014-07-1315:06:41

1476

收藏分类专栏：

\t"/u013480600/article/details/_blank"ACM--题解汇总

\t"/u013480600/article/details/_blank"图论--Floyd

文章标签：

\t"/u013480600/article/details/_blank"ACM

\t"/u013480600/article/details/_blank"algorithm

\t"/u013480600/article/details/_blank"算法版权POJ2263HeavyCargo(Floyd变形)\t"/u013480600/article/details/_blank"/problem?id=2263题意:

给你一个无向图,图中每条路有一个负重限制v.现在要你求从A点到B的的所有可能路径中,负重量最大的那个值(那条边的负重值).即假设从A到B有一条路径,该路径包括负重为10,20,30,5的4条路.那么该路径的负重就是5.现在我们要求一条负重值最大的路.分析:

此题可由floyd算法解.我们用d[i][j]表示从i到j的路径中的负重值最大者，且d[i][j]==0表示此路不通.每次用d[i][k]+d[k][j]更新d[i][j]时,我们都用大的值去更新小的值.这样得到的新路径的负重值自然更大.

其实这个思想就是floyd的动态规划思想,具体细节体会代码。AC代码:#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<map>#include<algorithm>#defineINF1e9usingnamespacestd;constintmaxn=200+10;intd[maxn][maxn];intn,m;voidfloyd(){for(intk=1;k<=n;k++)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(d[i][k]>0&&d[k][j]>0)d[i][j]=max(d[i][j],min(d[i][k],d[k][j]));}intcnt;map<string,int>mp;intID(strings){if(mp.find(s)==mp.end())mp[s]=++cnt;returnmp[s];}intmain(){intkase=0;while(scanf("%d%d",&n,&m)==2&&n&&m){cnt=0;mp.clear();for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)d[i][j]=i==j?INF:0;//0表示此路不通,无法负重while(m--){strings1,s2;intweight;cin>>s1>>s2>>weight;intu=ID(s1),v=ID(s2);d[u][v]=d[v][u]=weight;}floyd();strings1,s2;cin>>s1>>s2;intu=ID(s1),v=ID(s2);