(51)-POJ 2263 Heavy Cargo算法設(shè)計(jì)與分析

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

文章標(biāo)簽：

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

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

\t"/u013480600/article/details/_blank"算法版權(quán)POJ2263HeavyCargo(Floyd變形)\t"/u013480600/article/details/_blank"/problem?id=2263題意:

給你一個(gè)無向圖,圖中每條路有一個(gè)負(fù)重限制v.現(xiàn)在要你求從A點(diǎn)到B的的所有可能路徑中,負(fù)重量最大的那個(gè)值(那條邊的負(fù)重值).即假設(shè)從A到B有一條路徑,該路徑包括負(fù)重為10,20,30,5的4條路.那么該路徑的負(fù)重就是5.現(xiàn)在我們要求一條負(fù)重值最大的路.分析:

此題可由floyd算法解.我們用d[i][j]表示從i到j(luò)的路徑中的負(fù)重值最大者，且d[i][j]==0表示此路不通.每次用d[i][k]+d[k][j]更新d[i][j]時(shí),我們都用大的值去更新小的值.這樣得到的新路徑的負(fù)重值自然更大.

其實(shí)這個(gè)思想就是floyd的動(dòng)態(tài)規(guī)劃思想,具體細(xì)節(jié)體會(huì)代碼。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表示此路不通,無法負(fù)重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);