POJ 2263-Heavy Cargo Heavy Cargo Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3549 Accepted: 1894 Description Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive. Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities. Input The input will contain one or more test cases. The first line of each test case will contain two integers: the number of cities n (2<=n<=200) and the number of road segments r (1<=r<=19900) making up the street network. Then r lines will follow, each one describing one road segment by naming the two cities connected by the segment and giving the weight limit for trucks that use this segment. Names are not longer than 30 characters and do not contain white-space characters. Weight limits are integers in the range 0 – 10000. Roads can always be travelled in both directions. The last line of the test case contains two city names: start and destination. Input will be terminated by two values of 0 for n and r. Output For each test case, print three lines: a line saying “Scenario #x” where x is the number of the test case a line saying “y tons” where y is the maximum possible load a blank line Sample Input 4 3 Karlsruhe Stuttgart 100 Stuttgart Ulm 80 Ulm Muenchen 120 Karlsruhe Muenchen 5 5 Karlsruhe Stuttgart 100 Stuttgart Ulm 80 Ulm Muenchen 120 Karlsruhe Hamburg 220 Hamburg Muenchen 170 Muenchen Karlsruhe 0 0 Sample Output Scenario #1 80 tons Scenario #2 170 tons Source Ulm Local 1998
题意：给定一个公路核载图，图上标明了每一段公路载重限额，问从A地到B地最多能装载多少吨货物。这一题和POJ Problem 2240: Arbitrage有点相似，也是使用Floyd算法，稍作修改即可。
如上图所示，假设要从A到B，在用Floyd算法时，判断要不要借助C点，如果不借助，则load_ton[A][B]=80；如果借助C点，则路径变为A->C->B，A->C最多能载100吨，C->B最多能载90吨，所以总的来说，A->C->B最多能载min{100,90}=90吨；而90>80，所以借助C点后的载重大于不借助C点的载重，所以修改load_ton[A][B]=90。
知道这一点，我们可以很快的写出代码：
[cpp]
#include<iostream>
#include<map>
#include<string>
using namespace std;
const int MAX_N=202;
int load_ton[MAX_N][MAX_N];
//初始化数据
void init_load(int n)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
load_ton[i][j]=0;
}
//改造Floyd算法
void Floyd(int n)
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int min_ton=load_ton[i][k]<load_ton[k][j]?load_ton[i][k]:load_ton[k][j];//这条路上的最小值即为能通过的最大值
if(load_ton[i][j]<min_ton)
{
load_ton[i][j]=min_ton;//对称矩阵
load_ton[j][i]=min_ton;//对称矩阵
}
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
int n,r;
int case_num=1;
while(cin>>n>>r&&n&&r)
{
init_load(n);
map<string,int> city_index;//保存城市和下标的对应关系
string city1,city2;
int w;
int i=0;
while(r–)
{
cin>>city1>>city2>>w;
if(city_index.find(city1)==city_index.end())
city_index[city1]=i++;
if(city_index.find(city2)==city_index.end())
city_index[city2]=i++;
//load_ton[i-2][i-1]=w;//错，因为有可能cityi在之前已经加入了，这个时候i-1,i-2就不是cityi的下标了
//load_ton[i-1][i-2]=w;
load_ton[city_index[city1]][city_index[city2]]=w;//还是要从map里找对应下标
load_ton[city_index[city2]][city_index[city1]]=w;//因为路是两边通的，所以a[i][j]和a[j][i]相等
}
cin>>city1>>city2;
Floyd(n);
cout<<"Scenario #"<<case_num++<<endl;//
cout<<load_ton[city_index[city1]][city_index[city2]]<<" tons"<<endl<<endl;
}
return 0;
}
[/cpp]
本代码提交AC，用时79MS，内存316K。
在写代码的时候有几个小细节需要注意。在输入数据的时候，用MAP来保存城市和下标的关系，方便后面Floyd算法的操作；因为道路是双向通行的，所以保存数据时要保存成对称矩阵。
]]>