火车运输

题目描述 Description

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入描述 Input Description

第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意:x 不等于 y。

输出描述 Output Description

输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出-1。

样例输入 Sample Input

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

样例输出 Sample Output

3
-1
3

数据范围及提示 Data Size & Hint

对于 30%的数据,0 < n < 1,000,0 < m < 10,000,0 < q < 1,000;
对于 60%的数据,0 < n < 1,000,0 < m < 50,000,0 < q < 1,000;
对于 100%的数据,0 < n < 10,000,0 < m < 50,000,0 < q < 30,000,0 ≤ z ≤ 100,000。

求一下最大生成树,然后保持两点的深度相同找最近公共祖先(我打了一个暴力求最近公共祖先的方法,全过了)

时间: 08-20

火车运输的相关文章

NOIP 2013 火车运输【Kruskal + 树链剖分】

NOIP 2013 火车运输[树链剖分] 树链剖分 题目描述 Description A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路.每一条道路对车辆都有重量限制,简称限重.现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物. 输入描述 Input Description 第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路.接下来 m 行每行 3 个整数 x.y.z,每两个整数之间用一个空格隔开,表示

【CODEVS 3287】【NOIP2013】火车运输

http://codevs.cn/problem/3287/ 题目描述 国有 座城市,编号从 到 ,城市之间有 条双向道路.每一条道路对车辆都有重量限制,简称限重.现在有 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物. 输入格式 输入文件第一行有两个用一个空格隔开的整数 , 表示 国有 座城市和 条道路.接下来 行每行 个整数 ,每两个整数之间用一个空格隔开,表示从 号城市到 号城市有一条限重为 的道路.注意: 不等于 ,两座城市之间可能有多条道路.接下来一

NOIP2013火车运输[lca&amp;&amp;kruskal]

题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路.每一条道路对车辆都有重量限制,简称限重.现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物. 输入输出格式 输入格式: 输入文件名为 truck.in. 输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道 路. 接下来 m 行每行 3 个整数 x. y. z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z

luogu p1967 noip2013 火车运输

题目大意: 无向图上 每次询问两个点 寻找一条路径使这条路径上的最小值最大 思路: 先跑一个最大生成树 然后在最大生成树上每次对每两个点跑一个lca 在倍增的同时开一个数组a[i][j] 记录从i个点往上跑j条路里j条路中的最小值 然后每次lca的时候顺便记录一下就行了 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<c

小总结#1——最小边最大

给你n个点,m条边,让你求一条路径,使得s到t的最短边最长 这类问题,不是MST就是二分+判断 例如: 1.NOIP2013day1t3 火车运输   MST+树上倍增 2.CH ROUND 52 A 拆地毯  类似MST 3.BZOJ1614: [Usaco2007 Jan]Telephone Lines架设电话线 二分+判断+类似MST 4.NOI2014day1t2 部分分做法 枚举+MST 5. 小总结#1--最小边最大,布布扣,bubuko.com

Transportation poj1040

Ruratania is just entering capitalism and is establishing new enterprising activities in many fields in- cluding transport. The transportation company TransRuratania is starting a new express train from city A to city B with several stops in the stat

NOIp 2013 Day1 解题报告

NOIp 2013 Day1 解题报告 1.   转圈游戏 不难看出答案就是(x+m*10k) mod n 用快速幂算法,复杂度O(log2k) 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 //variable// 9 int n,m,x,

4G和3G到底有什么区别

同学的同学提出一个疑问:"4G和3G到底有什么区别?"我们整个宿舍哑口无言,唯一的回答是:"速度快--"(废话,速度快,这还用你说?!) 这是件多么令人惭愧的事啊,当非专业同学兴致勃勃地向我们请教一些专业问题时,许多情况下都得不到像样的回答,最终被"我们不学这个"搪塞过去.这些还都不是什么高深的问题,仅仅处于用户应用和体验层面. 于是我有了这样的念头,要把这些当初没有回答出来的问题好好回答一下,并且尽量用非专业的通俗语言.观众不在多少,至少是自己

刘志军的高铁遗产 ——看看日本高铁是怎么建起来的

加藤嘉一 我初到中国的时候,刘志军刚刚当上中国铁道部长,读后感“刘志军的高铁遗产 ——看看日本高铁是怎么建起来的 ”.八年来,我无数次乘坐中国火车到各地旅行,既坐过又脏又乱的普通列车,也坐过现代化的“和谐号”,将来肯定还会坐世界领先的京沪高铁.不过,中国高铁之父刘志军却没有机会以铁道部长的身份看到京沪高铁的开通了. 根据报道,他因在铁路建设中的“严重违纪行为”而落马下台,有永远出不来的可能.一直对中国高铁寄予高度关注,也确实没少加以表扬的世界媒体,在这个爆炸性的消息面前多少有些震惊.不过,作为新