首先，题目让我们求每个货车的最大运输量，翻译一下就是求路径上边权最小的边。
利用一下贪心思想可知，所有货车肯定都会尽量往大的边走。
进一步翻译，即为有一些小边货车根本不会走，或者说，我们只用知道点与点之间最大的连通路径就好了。
！！！
那么，我们求一下最大生成树，就可以知道最大连通图了。
然后来到第二步：求出了最大生成树，即树上点与点的路径只有一条，这条路也肯定是符合题目要求的。
那么，如何求出路径上最小的边？
暴力DFS？FLOYD？SPFA？
最快也是O（N＊Ｐ）的复杂度让你通通T掉！
因此，面对如此多的询问，考虑在线维护的做法，不考虑问一次遍历一次的做法。
于是，众神仙便想出了倍增的做法：
在倍增的时候维护一个w， 和倍增的f类似， w应该存储指向w方向的最小边。
每次询问时，快速倍增取min就好了。
#include <bits/stdc++.h> using namespace std; #define N 500010 #define INF (~0u>>1) inline int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-')s = -1; c = getchar(); } while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } return x * s; } struct edge{ // 临时存边 int u, v, dis; } e[N]; struct node{ int u, v, w; int next; } t[N]; int head[N]; int fa[N]; // 并查集 int n, m; int bian = 0; inline void add(int u, int v, int w){ t[++bian].u = u; t[bian].v = v; t[bian].w = w; t[bian].next = head[u]; head[u] = bian; return ; } bool cmp(edge a, edge b){ return a.dis > b.dis; } inline int find(int x){ if(x == fa[x])return fa[x]; else return fa[x] = find(fa[x]); } inline void kruskal(int n, int m){ // 求最大生成树 sort(e + 1, e + m + 1, cmp); for(int i = 1;i <= n; i++) fa[i] = i; // 并查集初始化 for(int i = 1;i <= m; i++){ int fau = find(e[i].u), fav = find(e[i].v); int u = e[i].u, v = e[i].v; if(fau != fav){ fa[fau] = fav; add(u, v, e[i].dis); add(v, u, e[i].dis); } } return ; } namespace LCA{ int deth[N], f[N][21]; int w[N][21]; bool vis[N]; void dfs(int now){ vis[now] = 1; for(int i = head[now]; i; i = t[i].next){ int v = t[i].v, u = t[i].u,dis = t[i].w; if(!vis[v]){ deth[v] = deth[now] + 1; w[v][0] = dis; // w 储存指向v的边权， 在 LCA 初始化时应变成 LCA 路径上的最小值 f[v][0] = now; // f0 即为自己的上一个 dfs(v); } } return ; } int lca(int x, int y){ if(find(x) != find(y))return -1; // 两个点不连通 int ans = INF; if(deth[x] > deth[y])swap(x, y); for(int i = 20; i >= 0;i--){ if(deth[f[y][i]] >= deth[x]){ ans = min(ans, w[y][i]); y = f[y][i]; // 先拉近距离 } } if(x == y)return ans; for(int i = 20;i >= 0; i--){//优先跳大的 if(f[x][i] != f[y][i]){ ans = min(ans, min(w[x][i], w[y][i])); // 更新 x = f[x][i]; y = f[y][i];//上跳 } } ans = min(ans, min(w[x][0], w[y][0])); // 更新 return ans; } void main(){ for(int i = 1;i <= n;i++){ // 恶心数据可能不连通 if(!vis[i]){ deth[i] = 1; dfs(i);//第一次储存信息 w[i][0] = INF;// 开头，不可能有 w f[i][0] = i;// 开头，本不配有 f。 因此存成自己 } } for(int i = 1;i <= 20; i++){ for(int j = 1;j <= n; j++){ f[j][i] = f[f[j][i-1]][i-1]; w[j][i] = min(w[j][i-1], w[f[j][i-1]][i-1]);//LCA初始化, w应保存 LCA路上指向j点方向的最小边 } } int q = read(); for(int i = 1;i <= q; i++){ int x = read(), y = read(); printf("%d ", lca(x, y)); } return ; } } int main(){ n = read(), m = read(); for(int i = 1;i <= m; i++){ int x = read(), y = read(), z = read(); e[i].u = x; e[i].v = y; e[i].dis = z;//第一次存储 } kruskal(n, m);//求最大生成树 LCA::main(); return 0; }
其实还有别的解法： 我的洛谷博客