c128 - 00544 - Heavy Cargo
題目描述
題目要求找出兩個城市之間路徑上的最小邊權最大值。換句話說，要找到一條路徑，使得路徑上所有邊的權重中，最小的那個權重最大。這相當於尋找最大瓶頸路徑。
解題思路
本題可以使用 Floyd-Warshall 演算法來解決。Floyd-Warshall 演算法可以計算圖中所有頂點對之間的最小距離（或最大距離，取決於初始化）。在本題中，我們將邊權視為道路的最大承載量，並使用 Floyd-Warshall 演算法計算所有城市對之間的最大承載量。 具體來說，我們首先將輸入的城市和道路建立成一個圖，其中城市作為頂點，道路作為邊，邊的權值為道路的最大承載量。然後，我們使用 Floyd-Warshall 演算法計算所有城市對之間的最大承載量。最後，我們輸出起點和終點城市之間的最大承載量。
複雜度分析
- 時間複雜度: O(n^3)，其中 n 是城市的數量。Floyd-Warshall 演算法的時間複雜度為 O(n^3)。
- 空間複雜度: O(n^2)，其中 n 是城市的數量。Floyd-Warshall 演算法需要一個 n x n 的矩陣來存儲城市對之間的距離。
程式碼
#include <iostream>
#include <map>
using namespace std;
int n,m,a[201][201],ip,v,ca;
string x,y;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> m){
if(n==0&&m==0)break;
ip=0;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
a[i][j]=0;
map <string,int> mp;
while(m--){
cin >> x >> y >> v;
if(mp.find(x)==mp.end())
mp[x]=ip++;
if(mp.find(y)==mp.end())
mp[y]=ip++;
a[mp[x]][mp[y]]=a[mp[y]][mp[x]]=v;
}
//Floyd-Warshall
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int k=0;k<n;++k){
a[j][k]=max(a[j][k],min(a[j][i],a[i][k]));
}
}
}
cin >> x >> y;
cout << "Scenario #" << ++ca << "\n" << a[mp[x]][mp[y]] << " tons\n\n";
}
}