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 
     
      #include 
      
       #define N 110int d[N][N];int n,m,s,t,num;int min(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;}