POJ 2263 Heavy Cargo(Floyd变形)

POJ 2263 Heavy Cargo(Floyd变形)

http://poj.org/problem?id=2263

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

分析:

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

其实这个思想就是floyd的动态规划思想.

AC代码:

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<map>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn = 200+10;
int d[maxn][maxn];
int n,m;
void floyd()
{
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=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]));
}
int cnt;
map<string,int> mp;
int ID(string s)
{
    if(mp.find(s)==mp.end())
        mp[s]=++cnt;
    return mp[s];
}
int main()
{
    int kase=0;
    while(scanf("%d%d",&n,&m)==2&&n&&m)
    {
        cnt=0;
        mp.clear();
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j] = i==j? INF:0;//0表示此路不通,无法负重
        while(m--)
        {
            string s1,s2;
            int weight;
            cin>>s1>>s2>>weight;
            int u = ID(s1),v=ID(s2);
            d[u][v]=d[v][u]=weight;
        }

        floyd();
        string s1,s2;
        cin>>s1>>s2;
        int u = ID(s1),v=ID(s2);
        printf("Scenario #%d\n",++kase);
        printf("%d tons\n\n",d[u][v]);
    }
    return 0;
}