UVa 544 Heavy Cargo

题目描述

题目要求在一个无向图中，找到从起点到终点的路径，使得路径上的最小边权最大（即最大化最小承载重量）。输出这个最大承载重量。

输入格式

每个测试用例第一行包含两个整数nnn（2≤n≤2002 \le n \le 2002≤n≤200）和rrr（1≤r≤199001 \le r \le 199001≤r≤19900）。接下来rrr行，每行两个城市名和一个整数权值（道路承载量）。最后一行两个城市名，表示起点和终点。输入以0 0结束。

输出格式

对于每个测试用例，输出Scenario #x，然后输出最大承载重量，后跟tons，最后输出一个空行。

样例

输入

4 3 Karlsruhe Stuttgart 100 Stuttgart Ulm 80 Ulm Muenchen 120 Karlsruhe Muenchen 5 5 Karlsruhe Stuttgart 100 Stuttgart Ulm 80 Ulm Muenchen 120 Karlsruhe Hamburg 220 Hamburg Muenchen 170 Muenchen Karlsruhe 0 0

输出

Scenario #1 80 tons Scenario #2 170 tons

题目分析

本题的核心是求解“最大瓶颈路径”，即最大化路径上的最小边权。可以使用类似Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall的变体或最大生成树（Maximum Spanning Tree\texttt{Maximum Spanning Tree}Maximum Spanning Tree）求解。

算法

• 初始时，weight[i][j]\textit{weight}[i][j]weight[i][j]表示iii到jjj的直接边权，若没有边则为000。
• 对于每个中间点kkk，更新：
  weight[i][j]=max⁡(weight[i][j],min⁡(weight[i][k],weight[k][j])) \textit{weight}[i][j] = \max(\textit{weight}[i][j], \min(\textit{weight}[i][k], \textit{weight}[k][j]))weight[i][j]=max(weight[i][j],min(weight[i][k],weight[k][j]))
• 最终weight[start][end]\textit{weight}[start][end]weight[start][end]即为答案。

复杂度分析

n≤200n \le 200n≤200，Floyd-Warshall\texttt{Floyd-Warshall}Floyd-WarshallO(n3)=8×106O(n^3) = 8 \times 10^6O(n3)=8×106，可接受。

代码实现

// Heavy Cargo// UVa ID: 544// Verdict: Accepted// Submission Date: 2016-08-10// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,r,weight[201][201],cases=0;while(cin>>n>>r,n&&r){map<string,int>cities;string start,end;inttons,count=1;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)weight[i][j]=weight[j][i]=-1;for(inti=1;i<=r;i++){cin>>start>>end>>tons;if(cities.find(start)==cities.end())cities[start]=count++;if(cities.find(end)==cities.end())cities[end]=count++;if(tons>weight[cities[start]][cities[end]]){weight[cities[start]][cities[end]]=tons;weight[cities[end]][cities[start]]=tons;}}for(intk=1;k<=n;k++)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(weight[i][k]!=-1&&weight[k][j]!=-1)weight[i][j]=max(weight[i][j],min(weight[i][k],weight[k][j]));cin>>start>>end;cout<<"Scenario #"<<++cases<<'\n';cout<<weight[cities[start]][cities[end]]<<" tons\n\n";}return0;}