[洛谷P1967][NOIP2013]货车运输

题目

题目描述

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

输入输出格式

输入格式:

第一行有两个用一个空格隔开的整数n,m表示A国有n座城市和m条道路。

接下来m行每行3个整数 x, y, z每两个整数之间用一个空格隔开,表示从x号城市到y号城市有一条限重为z的道路。注意:x不等于y,两座城市之间可能有多条道路 。

接下来一行有一个整数 q,表示有 q 辆货车需要运货。

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 。

输出格式:

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

输入输出样例

输入样例1:

输出样例1:

说明

对于 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

题解

部分内容摘自2013年鉴

其实这道题就是比较简单的图论题(作为最后一天的最后一题来讲)
首先对图做最大生成树(方法和最小生成树一样),得到的是一个森林。对于每一辆车,设其起点、终点分别为x,y,如果x,y连通,那么x,y在一棵树上,该火车最多能运送的货物为x,y之间的路径中的最小的边c。因为如果在原图中存在一条路径连接x,y,且所有的边的边权都大于c,那么最大生成树一定求错了(因为将该路径上的边加到生成树中去,必然形成包括c边在内的一个环,此时删除c边可以得到更大的生成树)
所以此题变成了求各个点对在树种路径上的最小边。

方法一:暴力

就是去实现上面的步骤,求LCA的时候暴力来求,不用倍增,可以AC(具体见暴力),如果是一条链的话会被卡,然而并没有这种数据。

方法二:倍增

此时我们可以用倍增的子项求某两个点的路径上的最小边。首先纪录每个点向上(向树根)走\(v(v=2^0,2^1,\dots)\)步所经过的路径中最小边是多少。对于一个询问x,y,可以求出其最近公共祖先z,然后求x,z之间的最小边和y,z之间的最小边。
时间复杂度为\(O(mlogm+n+logn)\)

方法三:

标称用的方法并不是倍增法,只需要在最大生成树的里面加一个求解的询问就行。首先用一个数组ans表示最终的答案,ans[i]表示第i个询问最多能运的货物数量。再用kruskal算法中,每将一条边加到最大生成树里面,那么这条边会将连个点集合并到一起。
如果某个询问i,他的两个点x,y分别属于这两个点集,那么这个询问的答案就是新加入的这条边的边权(因为此时x,y已经在一棵树中,所以x,y之间有路径。由于Kruskal求最大生成树时是由边权从大到小加入的,所以当前边是路径上边权最小的边)我们只需要在每个电商挂一个询问的链,每次询问时将两个询问的链合并到一起,合并的时候选取询问较少的那个链进行扫描并更新答案。所以对链的操作的时间复杂度为[合并次数+每次合并时扫描的询问个数和]。时间的小号主要在扫描,但是我们可以发现,每次扫描都只扫描了较少的那一部分,设长度为L,并且合并后询问的长度增长到2L以上。所以总的时间复杂度为\(O(mlogm+qlogq)\)

代码

LCA暴力,代码来自本校神犇yanyu

倍增

发表评论

电子邮件地址不会被公开。 必填项已用*标注