uva 10099 The Tourist Guide

DP(仿照Floyd)

这次是要找s到t的所有路径中，最小边的最大值，还是仿照Floyd，不过状态转移方程改一下，而且建图初始化也改一下就可以了(题目说了每条边的权都大于1)

建图邻接矩阵初始化为，d[i][j]=g[i][j]，不存在的边用0表示

状态转移方程

d[i][j]=min( d[i][j] , max(d[i][k] , d[k][j]) );

题目有一个很隐晦的地方就是，每次送旅客过去，导游也是要过去的（然后他自己再回来），所以没一趟导游都占了一个位置，如果大家觉得sample不对的话，那就是一个小问题了

#include <cstdio>
#include <cstring>
#define N 110
int d[N][N];
int n,m,s,t,num;

int min(int a ,int b)
{ return a<b?a:b; }
int max(int a, int b)
{ return a>b?a:b; }
void DP()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
             for(int j=1; j<=n; j++)
                 d[i][j]=max(d[i][j] , min(d[i][k],d[k][j]));
}
int main()
{
    int T=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(!n && !m)  break;
        memset(d,0,sizeof(d));
        for(int i=1; i<=m; i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            d[u][v]=d[v][u]=w;
        }
        scanf("%d%d%d",&s,&t,&num);
        DP();
        T++;
        printf("Scenario #%d\n",T);
        d[s][t]--;  //导游占了一个位置，实际上每次送过去的游客人数要少一位
        if((num%d[s][t]) == 0)
            printf("Minimum Number of Trips = %d\n",num/d[s][t]);
        else
            printf("Minimum Number of Trips = %d\n",(num/d[s][t])+1);
        printf("\n");

    }
    return 0;
}