POJ 1797 Heavy Transportation

时间:2022-08-24 20:20:52

题目链接:http://poj.org/problem?id=1797

Heavy Transportation
Time Limit: 3000MS   Memory Limit: 30000K
Total Submissions: 30840   Accepted: 8191

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 output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that Hugo can transport to the customer. Terminate the output for the scenario with a blank line.

Sample Input

1
3 3
1 2 3
1 3 4
2 3 5

Sample Output

Scenario #1:
4 题目大意:样例个数T,给定N个点,及M条边的最大负载,求顶点1到N的最大流。
     // 1.给定一个双向可达的有向图,求出1->n之间的所有可达路径,每条路径中的最小边的最大值。
AC代码:
 #include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int visit[];
int dis[];
int p[][];
int n;
int dijkstra()
{
int i,j,pos,minn;
for (i = ; i <= n; i ++)
{
dis[i] = p[][i];
visit[i] = ;
}
dis[] = ;
visit[] = ; for (i = ; i <= n; i ++)
{
minn = ;
for (j = ; j <= n; j ++)
{
if (!visit[j] && dis[j] > minn)
{
minn = dis[j];
pos = j;
}
}
visit[pos] = ;
for (j = ; j <= n; j ++)
{
if(!visit[j] && dis[j] < min(dis[pos],p[pos][j]))
dis[j] = min(dis[pos],p[pos][j]);
}
}
return dis[n];
}
int main()
{
int t,m,x,y,z,i,j,f = ;
scanf("%d",&t);
while (t --)
{
scanf("%d%d",&n,&m);
for (i = ; i <= n; i ++)
for (j = ; j <= n; j ++)
p[i][j] = ;
for (i = ; i < m; i ++)
{
scanf("%d%d%d",&x,&y,&z);
p[x][y] = p[y][x] = z;
}
printf("Scenario #%d:\n",f ++);
printf("%d\n\n",dijkstra()); //注意格式
}
}
 

POJ 1797 Heavy Transportation的更多相关文章

  1. poj 1797 Heavy Transportation(最大生成树)

    poj 1797 Heavy Transportation Description Background Hugo Heavy is happy. After the breakdown of the ...

  2. POJ 1797 Heavy Transportation &sol; SCU 1819 Heavy Transportation (图论,最短路径)

    POJ 1797 Heavy Transportation / SCU 1819 Heavy Transportation (图论,最短路径) Description Background Hugo ...

  3. POJ&period;1797 Heavy Transportation &lpar;Dijkstra变形&rpar;

    POJ.1797 Heavy Transportation (Dijkstra变形) 题意分析 给出n个点,m条边的城市网络,其中 x y d 代表由x到y(或由y到x)的公路所能承受的最大重量为d, ...

  4. POJ 1797 Heavy Transportation SPFA变形

    原题链接:http://poj.org/problem?id=1797 Heavy Transportation Time Limit: 3000MS   Memory Limit: 30000K T ...

  5. POJ 1797 &Tab;Heavy Transportation (Dijkstra变形)

    F - Heavy Transportation Time Limit:3000MS     Memory Limit:30000KB     64bit IO Format:%I64d & ...

  6. POJ 1797 ——Heavy Transportation——————【最短路、Dijkstra、最短边最大化】

    Heavy Transportation Time Limit:3000MS     Memory Limit:30000KB     64bit IO Format:%I64d & %I64 ...

  7. POJ 1797 Heavy Transportation &lpar;最大生成树&rpar;

    题目链接:POJ 1797 Description Background Hugo Heavy is happy. After the breakdown of the Cargolifter pro ...

  8. POJ 1797 Heavy Transportation &lpar;Dijkstra&rpar;

    题目链接:POJ 1797 Description Background Hugo Heavy is happy. After the breakdown of the Cargolifter pro ...

  9. POJ 1797 Heavy Transportation(最大生成树&sol;最短路变形)

    传送门 Heavy Transportation Time Limit: 3000MS   Memory Limit: 30000K Total Submissions: 31882   Accept ...

随机推荐

  1. 安卓开发&lowbar;慕课网&lowbar;Fragment实现Tab&lpar;App主界面&rpar;

    学习内容来自“慕课网” 这里用Fragment来实现APP主界面 思路: 底部横向排列4个LinearLayout,每个LinearLayout包含一个图片按钮和一个文字 1.默认显示第一个功能(微信 ...

  2. ELF Format 笔记(九)—— Elf32&lowbar;Sym 结构的 st&lowbar;value 和 st&lowbar;shndx 成员

    ilocker:关注 Android 安全(新手) QQ: 2597294287 前面的笔记中提到过 Elf32_Sym 结构,本篇笔记再写一下其中的 st_value 和 st_shndx 成员. ...

  3. HDU3068 最长回文 Manacher算法

    Manacher算法是O(n)求最长回文子串的算法,其原理很多别的博客都有介绍,代码用的是clj模板里的,写的确实是异常的简洁,现在的我只能理解个大概,下面这个网址的介绍比较接近于这个模板,以后再好好 ...

  4. Zabbix探索:工作时间的设置

    默认情况下,Zabbix的工作时间是启用的. 启用后,图形的北京在工作时间内就是白底的,否则就是灰底的. 今天纠结了半天,因为无论如何都是灰底的. 后来连接到服务器上一看,靠,忘记同步时间了,所以刚好 ...

  5. delete删除多表

    1.DELETE a.*, aa.* FROM student a, person aa WHERE a.id = aa.city_id AND a.name = '' 2.DELETE a.*, a ...

  6. &lpar;转&rpar;ThinkPHP find方法 查询一条数据记录

    find() ThinkPHP find() 方法是和 select() 用法类似的一个方法,不同之处 find() 查询出来的始终只有一条数据,即系统自动加上了 LIMIT 1 限制. 当确认查询的 ...

  7. solr常用命令

    1.启动和关闭 a.启动和重启 启动和重启命令有很多选项让你运行在SolrCloud模式,使用示例配置,以hostname为开头或者非默认端口,指向本地ZooKeeper. bin/solr star ...

  8. Spring 工作原理

    1.spring原理 内部最核心的就是IOC了,动态注入,让一个对象的创建不用new了,可以自动的生产,这其实就是利用java里的反射,反射其实就是在运行时动态的去创建.调用对象,Spring就是在运 ...

  9. js将时间戳转成格式化的时间

    function getLocalTime(nS){ return new Date(parseInt(nS) * 1000).toLocaleString().replace(/年|月/g, &qu ...

  10. js杨辉三角控制台输出

    function Yang(line){ var arr=new Array() ;i<=line;i++){ ]==undefined){arr[i-]=[];} ){arr[]=[i]}){ ...