E - Heavy Transportation
来源poj1797
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
要求你算出从1到n的道路,找出能运最大的重量,最大生成树,用了prim算法,额一开始没看到到n,以为是到任意一个地方,wa了
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iomanip>
#include<cmath>
#include<float.h>
#include<string.h>
#include<algorithm>
#define sf scanf
#define pf printf
#define mm(x,b) memset((x),(b),sizeof(x))
#include<vector>
#include<queue>
#include<stack>
#include<map>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
typedef long long ll;
const ll mod=1e9+100;
const double eps=1e-8;
using namespace std;
const double pi=acos(-1.0);
const int inf=0xfffffff;
const int N=1005;
int visit[N],Map[N][N],dist[N];
int prim(int n)
{
int pos,ans=inf;
rep(i,1,n+1)
dist[i]=Map[1][i];
visit[1]=1;
dist[1]=0;
rep(i,1,n+1)
{
int max1=-inf;
rep(j,1,n+1)
if(visit[j]==0&&dist[j]>max1)
{
max1=dist[j];
pos=j;
}
visit[pos]=1;
ans=min(max1,ans);
if(pos==n) break;
rep(j,1,n+1)
if(visit[j]==0&&dist[j]<Map[pos][j])
dist[j]=Map[pos][j];
}
return ans;
}
int main()
{
int re,cas=1,n,m,x,y,k;
cin>>re;
while(re--)
{
sf("%d%d",&n,&m);
mm(visit,0);
mm(Map,0);
mm(dist,0);
while(m--)
{
sf("%d%d%d",&x,&y,&k);
Map[x][y]=Map[y][x]=k;
}
pf("Scenario #%d:\n%d\n\n",cas++,prim(n));
}
// pf("\n");
return 0;
}
最新文章
- Atitit &#160;图像处理Depixelizing&#160;Pixel&#160;Art像素风格画的矢量化
- ps切图抠图详解-web前端(转)
- iOS边练边学--AFNetWorking框架GET、Post、Download、Upload,数据解析模式以及监控联网状态
- Java魔法堂:注释和注释模板 (转)
- 【Oracle XE系列之三】使用OMF方式手工创建Oracle XE数据库
- C# TextBox 只能输入数字
- 【工具篇】利用DBExportDoc V1.0 For MySQL自动生成数据库表结构文档
- Android中常用的URI
- node笔记-node的好基友monggoDB
- 数据拆分之 垂直拆分 and 水平拆分
- DDoS攻击、CC攻击的攻击方式和防御方法
- HashMap的源码,实现原理,底层结构
- Innodb锁相关总结
- FFmpeg数据结构AVFrame
- Ex 5_21 无向图G=(V,E)的反馈边集..._第九次作业
- ASP.NET自定义错误页并返回正确的500、404状态码
- 转:.net设计模式之工厂模式
- JQuery Validate插件与实现
- UVA11401 Triangle Counting
- oracle 错误实例分析(ORA-01078)
热门文章
- Ajax发送请求,并接受字符串
- 通过Pdf预览Excel或者word或者Powerpoint (C#将Office转换为PDF)
- Mysql中DDL, DML, DCL, 和TCL是什么?
- Map network drive遇到报错&ldquo;The network folder specified is currently mapped using a different user name and password&rdquo;,怎么办?
- ImportError: No module named _tkinter on macos
- SSE图像算法优化系列八:自然饱和度(Vibrance)算法的模拟实现及其SSE优化(附源码,可作为SSE图像入门,Vibrance算法也可用于简单的肤色调整)。
- 分享12款令人瞠目结舌的WebVR演示和实验效果
- 一行代码搞定 R 语言模型输出!(使用 stargazer 包)
- Python性能分析
- GOF提出的23种设计模式是哪些 设计模式有创建形、行为形、结构形三种类别 常用的Javascript中常用设计模式的其中17种 详解设计模式六大原则