题目链接:POJ 1797
Description
Background
Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.
Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know.
Problem
You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo's place) to crossing n (the customer's place). You may assume that there is at least one path. All streets can be travelled in both directions.
Input
The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings.
Output
The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings.
Sample Input
1
3 3
1 2 3
1 3 4
2 3 5
Sample Output
Scenario #1:
4
Source
TUD Programming Contest 2004, Darmstadt, Germany
Solution
题意
有 N 个城市,M 条道路,Hugo Heavy 要从城市 1 到城市 N 运输货物,每条道路都有它的最大载重量,求从城市 1 到城市 N 运送最多的重量是多少。
思路
最大生成树
题目要求点 1 到 N 的所有路径的所有边权的最小值中的最大值。维护一个最大生成树,不断将最大权值的边加入,如果遇到点 N 就结束。
这题有点坑,输出两个换行。
此题还可以用 \(Dijkstra\) 解决。戳这里
Code
Prim
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> P;
int n, m;
int ans;
struct Edge {
int to, w;
Edge(int to, int w): to(to), w(w) {}
};
vector<Edge> G[N];
int d[N], v[N];
void init() {
for(int i = 0; i < N; ++i) {
G[i].clear();
}
ans = inf;
}
void add(int x, int y, int z) {
G[x].push_back(Edge(y, z));
}
void prim(int s) {
priority_queue<P> q;
memset(d, 0, sizeof(d));
memset(v, 0, sizeof(v));
d[s] = inf;
q.push(P(inf, s));
while(q.size()) {
P p = q.top(); q.pop();
int x = p.second;
if(v[x]) continue;
v[x] = 1;
ans = min(ans, p.first);
if(x == n) return;
for(int i = 0; i < G[x].size(); ++i) {
Edge e = G[x][i];
if (d[e.to] < e.w && !v[e.to]) {
d[e.to] = e.w;
q.push(P(d[e.to], e.to));
}
}
}
}
int main() {
int T;
scanf("%d", &T);
int kase = 0;
while(T--) {
init();
scanf("%d%d", &n, &m);
for(int i = 0; i < m; ++i) {
int x, y, z;
scanf("%d%d%d", &x, & y, &z);
add(x, y, z);
add(y, x, z);
}
prim(1);
if(kase) printf("\n");
printf("Scenario #%d:\n", ++kase);
printf("%d\n", ans);
}
return 0;
}
Kruskal
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010, M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int ans;
struct Edge {
int x, y, z;
} edge[M];
int fa[N];
int cmp(Edge a, Edge b) {
return a.z > b.z;
}
int get(int x) {
if(x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
void init() {
for(int i = 0; i <= n; ++i) {
fa[i] = i;
}
ans = inf;
}
void kruskal() {
sort(edge + 1, edge + 1 + m, cmp);
for(int i = 1; i <= m; ++i) {
int x = get(edge[i].x);
int y = get(edge[i].y);
if(x != y) {
ans = min(ans, edge[i].z);
fa[x] = y;
}
x = get(1);
y = get(n);
if(x == y) return;
}
}
int main() {
int T;
scanf("%d", &T);
int kase = 0;
while(T--) {
scanf("%d%d", &n, &m);
init();
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);
}
kruskal();
if(kase) printf("\n");
printf("Scenario #%d:\n", ++kase);
printf("%d\n", ans);
}
return 0;
}
POJ 1797 Heavy Transportation (最大生成树)的更多相关文章
-
poj 1797 Heavy Transportation(最大生成树)
poj 1797 Heavy Transportation Description Background Hugo Heavy is happy. After the breakdown of the ...
-
POJ 1797 Heavy Transportation / SCU 1819 Heavy Transportation (图论,最短路径)
POJ 1797 Heavy Transportation / SCU 1819 Heavy Transportation (图论,最短路径) Description Background Hugo ...
-
POJ.1797 Heavy Transportation (Dijkstra变形)
POJ.1797 Heavy Transportation (Dijkstra变形) 题意分析 给出n个点,m条边的城市网络,其中 x y d 代表由x到y(或由y到x)的公路所能承受的最大重量为d, ...
-
POJ 1797 Heavy Transportation
题目链接:http://poj.org/problem?id=1797 Heavy Transportation Time Limit: 3000MS Memory Limit: 30000K T ...
-
POJ 1797 Heavy Transportation SPFA变形
原题链接:http://poj.org/problem?id=1797 Heavy Transportation Time Limit: 3000MS Memory Limit: 30000K T ...
-
POJ 1797 Heavy Transportation(最大生成树/最短路变形)
传送门 Heavy Transportation Time Limit: 3000MS Memory Limit: 30000K Total Submissions: 31882 Accept ...
-
POJ 1797 	Heavy Transportation (Dijkstra变形)
F - Heavy Transportation Time Limit:3000MS Memory Limit:30000KB 64bit IO Format:%I64d & ...
-
POJ 1797 ——Heavy Transportation——————【最短路、Dijkstra、最短边最大化】
Heavy Transportation Time Limit:3000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64 ...
-
POJ 1797 Heavy Transportation (Dijkstra)
题目链接:POJ 1797 Description Background Hugo Heavy is happy. After the breakdown of the Cargolifter pro ...
随机推荐
-
infopath发布的提示“无法解析SOAP消息”(The SOAP message cannot be parsed)问题解决方案
最近发现一个列表数据过大,每次发布infopath表单提示如下错误: 后来发现一个infopath表单通过list.asmx and Formsservice.asmx来进行发布的. This err ...
-
asp.net 页面 输出之前修改 html(render)
protected override void Render(HtmlTextWriter writer) { StringWriter output = new StringWriter(); ba ...
-
php实现返回上一页的功能的3种有效方法
php实现返回上一页的功能的3种有效方法 header(location:你的上一页的路径); // 注意这个函数前不能有输出 header(location:.getenv("HT ...
-
Qt使用AES加密算法对字符串进行加密
因工作需要,需要对字符串进行加密处理,在网上找了很长时间,终于找到了一个可以使用的aes加密算法.其源代码采用c++编写而成,但其头文件引用windows.h,经过修改部分代码,将#inc ...
-
关于echo双引号和单引号的问题
echo ''; 输出的是变量符号和变量名称. echo"";输出的是变量的值. <?php $s="PAP"; echo "my name i ...
-
零行代码为App添加异常加载占位图
前文提要 近期准备重构项目,需要重写一些通用模块,正巧需要设置App异常加载占位图的问题,心血来潮设想是否可以零行代码解决此问题,特在此分享实现思路. 思路分享 对于App占位图,通常需要考虑的控件有 ...
-
Nginx宣布正式支持gRPC,附示例代码
原创 2018-03-20 薛命灯 聊聊架构 作者|Owen Garrett编辑|薛命灯 NGINX 官方博客正式宣布 NGINX 支持原生的 gPRC,现在就可以从代码仓库拉取快照版本.该特性将会被 ...
-
ABP框架系列之二十四:(Email-Sending-EF-电子邮件发送)
Introduction Email sending is a pretty common task for almost every application. ASP.NET Boilerplate ...
-
python之if循环
if 条件: if语句块else: 语句块 money = int(input("请输入你兜里的钱:")) if money > 500: print("吃肉&qu ...
-
hdoj5785
题意:略 先用题解的办法,manacher,然后tag,add数组.但是比较难办的是manacher加了新的字符.这样的话cntL和cntR不是实际的值,但是没关系,原本的字符都在奇数位置,这样cnt ...