DP(仿照Floyd)

uva 10048 Audiophobia? 一樣的題目啊

這次是要找s到t的所有路徑中，最小邊的最大值，還是仿照Floyd，不過狀態(tài)轉(zhuǎn)移方程改一下，而且建圖初始化也改一下就可以了(題目說了每條邊的權(quán)都大于1)

建圖鄰接矩陣初始化為，d[i][j]=g[i][j]，不存在的邊用0表示

狀態(tài)轉(zhuǎn)移方程

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

題目有一個很隱晦的地方就是，每次送旅客過去，導(dǎo)游也是要過去的（然后他自己再回來），所以沒一趟導(dǎo)游都占了一個位置，如果大家覺得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]--; //導(dǎo)游占了一個位置，實際上每次送過去的游客人數(shù)要少一位if((num%d[s][t]) == 0)printf("Minimum Number of Trips = %d\n",num/d[s][t]);elseprintf("Minimum Number of Trips = %d\n",(num/d[s][t])+1);printf("\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的uva 10099 The Tourist Guide的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。