题目

题目描述

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

倍增