洛谷题单<最小生成树> 货车运输
首先题目要求路径中的最大的最小值 所以建立最大生成图那么唯一路径中的最小值就是题目答案
又因为如果使用dfs/bfs求最小值的话 时间复杂度是 O(n * q) 会超时 所以使用lca(最近公共祖先)的思路求路径最小值。不了解的话建议在ACwing 上y总在提高课中有讲到(安利一波)或者阅读:https://blog.csdn.net/jeryjeryjery/article/details/52853017
我们在裸的模板 上还要在维护 wmin 数组 (wmin[a][i] 表示a点向上找2^i个祖先的最短边)
建议lca建树的dfs 写成bfs 因为dfs有爆栈的风险。
代码如下:
#include<bits/stdc++.h> using namespace std; const int N = 10010, M = 50010; struct edge{ int a, b, c; bool operator<(const edge& t)const{ return c > t.c; } }edges[M]; int h[N], e[M], ne[M], w[M], idx; //邻接表存最大生成树 int p[N], father[N][25], wmin[N][25], depth[N];//邻接表 ;lca 倍增求法 int n, m, st[N]; int find(int x){ if(x == p[x]) return x; else return p[x] = find(p[x]); } void add(int a, int b, int c){ e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++; } void kruskal(){ sort(edges, edges + m); for(int i = 0; i <= n; i++) p[i] = i; for(int i = 0; i < m; i ++){ int a = edges[i].a, b = edges[i].b, c = edges[i].c; int x = find(a), y = find(b); if(x != y){ p[x] = y; add(a, b, c); add(b, a, c); } } } void bfs(int k){ st[k] = 1; queue<int> q; q.push(k); while(q.size()){ int son = q.front(); q.pop(); for(int i = h[son]; i != -1; i = ne[i]){ int j = e[i]; if(!st[j]){ q.push(j); st[j] = 1; depth[j] = depth[son] + 1; father[j][0] = son; wmin[j][0] = w[i]; for(int i = 1; i <= 20; i++){ father[j][i] = father[father[j][i-1]][i-1]; wmin[j][i] = min(wmin[j][i-1], wmin[father[j][i-1]][i-1]);//更新father 和 wmin 数组; } } } } } int lca(int a, int b){ int ans = 0x3f3f3f3f; if(find(a) != find(b)) return -1; if(depth[a] < depth[b]) swap(a, b); for(int i = 20; i >= 0; i--){ if(depth[father[a][i]] >= depth[b]){ ans = min(ans, wmin[a][i]); a = father[a][i]; } } if(a == b) return ans; for(int i = 20; i >= 0; i--){ if(father[a][i] != father[b][i]){ ans = min(ans, min(wmin[a][i], wmin[b][i])); a = father[a][i]; b = father[b][i]; } } ans = min(ans, min(wmin[a][0], wmin[b][0])); return ans; } int main(){ cin >> n >> m; memset(h, -1, sizeof h); for(int i = 0; i < m; i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); edges[i] = {a, b, c}; } kruskal(); for(int i = 1; i <= n; i++){ if(!st[i]){ depth[i] = 1; bfs(i); } } int query; cin >> query; while(query --){ int a, b; scanf("%d%d", &a, &b); int ans = lca(a, b); printf("%d\n", ans); } return 0; }