http://poj.org/problem?id=2263

題意：汽車的載重量沒有限制，取決于道路的承載能力，求起點到終點所經過的路徑不會超過道路的承載限制。

分析：本題并不是求最短路徑，而是求通過的能力最大的路，這種路可以稱作最大容量路，可以用floyd算法的思想求解。設城市i到城市j的承載能力記為【i，j】,初始時K到M沒有直接路徑，因此k到M的承載重量為0。即【K,M】=0.加入中間結點H后，K到M的承載重量改為MAX｛【K,M】,MIN([K,H],[H,K])｝;

View Code 1 // I'm the Topcoder 2 //C 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 #include <ctype.h> 7 #include <math.h> 8 #include <time.h> 9 //C++ 10 #include <iostream> 11 #include <algorithm> 12 #include <cstdio> 13 #include <cstdlib> 14 #include <cmath> 15 #include <cstring> 16 #include <cctype> 17 #include <stack> 18 #include <string> 19 #include <list> 20 #include <queue> 21 #include <map> 22 #include <vector> 23 #include <deque> 24 #include <set> 25 using namespace std; 26 27 //*************************OUTPUT************************* 28 #ifdef WIN32 29 #define INT64 "%I64d" 30 #define UINT64 "%I64u" 31 #else 32 #define INT64 "%lld" 33 #define UINT64 "%llu" 34 #endif 35 36 //**************************CONSTANT*********************** 37 #define INF 0x3f3f3f3f 38 #define eps 1e-8 39 #define PI acos(-1.) 40 #define PI2 asin (1.); 41 typedef long long LL; 42 //typedef __int64 LL; //codeforces 43 typedef unsigned int ui; 44 typedef unsigned long long ui64; 45 #define MP make_pair 46 typedef vector<int> VI; 47 typedef pair<int, int> PII; 48 #define pb push_back 49 #define mp make_pair 50 51 //***************************SENTENCE************************ 52 #define CL(a,b) memset (a, b, sizeof (a)) 53 #define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b)) 54 #define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c)) 55 56 //****************************FUNCTION************************ 57 template <typename T> double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); } 58 template <class T> inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; } 59 template <typename T> inline T square(T va, T vb) { return va * va + vb * vb; } 60 61 // aply for the memory of the stack 62 //#pragma comment (linker, "/STACK:1024000000,1024000000") 63 //end 64 65 #define maxcities 256+10 66 int kase=0;//測試數據序號 67 int n,r; 68 int w[maxcities][maxcities];//floyd算法中A矩陣 69 char city[maxcities][30+10];//城市名 70 char start[30+10],dest[30+10]; 71 72 int numcities;//城市名在city數組中的序號 73 74 75 //把陸陸續續進來的城市名存儲到city數組中,index函數的功能是給定一個城市名 76 //返回它在city數組中的下標,if不存在,則把該城市名追加到city數組中 77 int index(char* s){ 78 int i; 79 for(i=0;i<numcities;i++){ 80 if(!strcmp(city[i],s)) return i; 81 } 82 strcpy(city[i],s); 83 numcities++; 84 return i; 85 } 86 87 88 //讀入測試數據 89 int read_case(){ 90 int limit; 91 scanf("%d%d",&n,&r); 92 if(n==0 ) return 0; 93 //初始化數組 94 for(int i=0;i<n;i++){ 95 for(int j=0;j<n;j++){ 96 w[i][j]=0; 97 } 98 } 99 for(int i=0;i<n;i++) w[i][i]=INF; 100 //讀入道路網絡 101 numcities=0; 102 for(int k=0;k<r;k++){ 103 scanf("%s%s%d",start,dest,&limit); 104 int i=index(start); 105 int j=index(dest); 106 w[i][j]=w[j][i]=limit;//floyd算法中矩陣A的初始值就是鄰接矩陣 107 } 108 //讀入起始城市和終點城市 109 scanf("%s%s",start,dest); 110 return 1; 111 } 112 113 void floyd(){ 114 for(int k=0;k<n;k++){ 115 for(int i=0;i<n;i++){ 116 for(int j=0;j<n;j++){ 117 w[i][j]=max(w[i][j],min(w[i][k],w[k][j])); 118 } 119 } 120 } 121 } 122 123 void solve_case(){ 124 //floyd() 125 floyd(); 126 int i=index(start); 127 int j=index(dest); 128 printf("Scenario #%d\n",++kase); 129 printf("%d tons\n\n",w[i][j]); 130 } 131 132 int main(){ 133 while(read_case()){ 134 solve_case(); 135 } 136 return 0; 137 }

?

轉載于:https://www.cnblogs.com/lanjiangzhou/archive/2013/03/24/2979809.html

總結

以上是生活随笔為你收集整理的POJ 2263 floyd思想的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。