# P1967 货车运输

xiaoxiao2021-02-28  2

## 题目描述

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

## 说明

lca倍增（据说是模板题）

#include<bits/stdc++.h> using namespace std; int n , m; const int MAXN = 100000 + 10; int g[MAXN] , u[2 * MAXN] , v[2 * MAXN] , w[2 * MAXN] , First[2 * MAXN] , Next[2 * MAXN]; int fa[MAXN][21] , ff[MAXN][21] , deep[MAXN]; int inf = 0x7fffffff; struct f { int x; int y; int c; }a[MAXN] ; int com(const f &u , const f &v) { return u.c > v.c; } int bin(int x ) { while(x != g[x]) x = g[x] = g[g[x]]; return x; } void kruskal() { int num = 0; for(int i = 1; i <= m ; i ++) { int x = bin(a[i].x); int y = bin(a[i].y); if(x != y) { g[y] = x; num ++; u[num] = a[i].x; v[num] = a[i].y ; w[num] = a[i].c; Next[num] = First[u[num]]; First[u[num]] = num; u[num + n - 1] = a[i].y ; v[num + n - 1] = a[i].x; w[num + n - 1] = w[num]; Next[num + n - 1] = First[u[num + n - 1]];First[u[num + n - 1]] = num + n - 1; if(num == n - 1) break; } } } void dfs(int q) { for(int k = First[q] ; k != -1; k = Next[k]) { int to = v[k]; if(deep[to] == 0) { deep[to] = deep[q] + 1; fa[to][0] = q; ff[to][0] = w[k]; dfs(to); } } } void ycl() { for(int i = 1; i <= n ; i ++) { if(deep[i] == 0) { deep[i] = 1; fa[i][0] = 0; dfs(i); } } dfs(1); for(int i = 1; i <= 20 ; i ++) { for(int j = 1; j <= n ; j ++) { fa[j][i] = fa[fa[j][i-1]][i-1]; ff[j][i] = min(ff[j][i-1],ff[fa[j][i-1]][i-1]); } } } int lca(int x , int y) { int ans = inf; if(deep[x] < deep[y]) { swap(x , y); } for(int i = 20 ; i >= 0 ; i --) { if(deep[fa[x][i]] >= deep[y]) { ans = min (ans , ff[x][i]); x = fa[x][i]; } } if(x == y) return ans; for(int i = 20 ; i >= 0 ; i --) { if(fa[x][i] != fa[y][i]) { ans = min (ans , min(ff[x][i] , ff[y][i])); x = fa[x][i]; y = fa[y][i]; } } ans = min (ans, min (ff[x][0] , ff[y][0])); return ans; } int main() { cin >> n >> m; for(int i = 1; i <= n ; i ++) { g[i] = i; First[i] = -1; } for(int i = 1 ; i <= m ; i ++) { scanf("%d %d %d" , &a[i].x , &a[i].y , &a[i].c); } sort( a + 1, a + m + 1, com); kruskal(); ycl(); int T; cin >> T; while(T --) { int x , y; scanf("%d %d" , &x , &y); if(bin(x) != bin(y)) { printf("-1\n"); } else { printf("%d\n",lca(x,y)); } } return 0; }