UVa 544 Heavy Cargo

题目描述题目要求在一个无向图中找到从起点到终点的路径使得路径上的最小边权最大即最大化最小承载重量。输出这个最大承载重量。输入格式每个测试用例第一行包含两个整数nnn2≤n≤2002 \le n \le 2002≤n≤200和rrr1≤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≤200Floyd-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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,r,weight[201][201],cases0;while(cinnr,nr){mapstring,intcities;string start,end;inttons,count1;for(inti1;in;i)for(intj1;jn;j)weight[i][j]weight[j][i]-1;for(inti1;ir;i){cinstartendtons;if(cities.find(start)cities.end())cities[start]count;if(cities.find(end)cities.end())cities[end]count;if(tonsweight[cities[start]][cities[end]]){weight[cities[start]][cities[end]]tons;weight[cities[end]][cities[start]]tons;}}for(intk1;kn;k)for(inti1;in;i)for(intj1;jn;j)if(weight[i][k]!-1weight[k][j]!-1)weight[i][j]max(weight[i][j],min(weight[i][k],weight[k][j]));cinstartend;coutScenario #cases\n;coutweight[cities[start]][cities[end]] tons\n\n;}return0;}