Poj2263 Heavy Cargo

题目大意：给出每个城市之间的距离，让你求卡车能通过的边中的最大载重量。

算法思路：在所有的通路中求最小边长的最大值（类似于poj2253）http://huyifan951124.iteye.com/blog/2314976。由于点的个数比较小，又是对给定的任意两个点求值，因此我们可以用floyd算法，当然也可以使用网络流。

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
using namespace std;

int n,m;
char str1[50];
char str2[50];
int a[205][205];
int weight;

int main()
{
    int sym=0;
    while(true)
    {
        sym++;
        map<string,int>mp;
        memset(a,0,sizeof(a));
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)
            break;
        int num=1;
        for(int i=0;i<m;i++)
        {
            scanf("%s%s%d",str1,str2,&weight);
            if(mp.find(str1)==mp.end())
            {
                mp[str1]=num++;
            }
            if(mp.find(str2)==mp.end())
            {
                mp[str2]=num++;
            }
            a[mp[str1]][mp[str2]]=weight;
            a[mp[str2]][mp[str1]]=weight;

        }
        scanf("%s%s",str1,str2);

        int t1=mp[str1],t2=mp[str2];

        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    //最小边里的最大值
                    int flag=min(a[i][k],a[k][j]);
                    a[i][j]=max(a[i][j],flag);
                }
            }
        }
        printf("Scenario #%d\n",sym);
        printf("%d tons\n\n",a[t1][t2]);
    }
    return 0;
}