【题解】LuoGu1967：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。

样例输入
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
样例输出
3
-1
3
对于 100%的数据，0 < n <10,000，0 < m < 50,000，0< q < 30,000，0 ≤ z ≤ 100,000。

【题解】
由题意可知：每辆车的最大载重就是道路的最小值的最大值
那么要找到这个最小值的最大值就要用到最大生成树，又发现只有最大生成树的边是有用的，其他的便是没用的，这样使得整张图变成了森林（即不存在环）
最大生成树当然使用kruskal的

构图已经会了，现在的问题是如何找出最小值的最大值。
首先判断-1的情况——若两点没联通，即输出-1。那么就用并查集判断就可以了，因为前面kruskal已经做好了
然后，想到暴力：从一个点走到另一个点
发现每辆车一定是跑最短路的，所以想到倍增求LCA了

Code：

const maxn = 50010;
var
    edge:array[0..maxn*2] of record
        t,next,dis:longint;
    end;
    head,f,d,x,y,z:array[0..maxn*2] of longint;
    fa,w:array[0..maxn,0..30] of longint;
    vis:array[0..maxn] of boolean;
    n,m,q,i,num,xx,yy:longint;

function get(k:longint):longint;

begin
    if f[k] <> k then f[k] := get(f[k]);
    get := f[k];
end;

procedure swap(var x,y:longint);
var
    tmp:longint;

begin
    tmp := x; x := y; y := tmp;
end;

function min(x,y:longint):longint;

begin
    if x < y then exit(x) else exit(y);
end;

procedure sort(l,r:longint);
var
    i,j,mid:longint;

begin
    i := l; j := r; mid := z[(l + r) >> 1];
    repeat
        while z[i] > mid do inc(i);
        while z[j] < mid do dec(j);
        if i <= j then
        begin
            swap(x[i],x[j]);
            swap(y[i],y[j]);
            swap(z[i],z[j]);
            inc(i); dec(j);
        end;
    until i > j;
    if i < r then sort(i,r);
    if l < j then sort(l,j);
end;

procedure add(x,y,z:longint);//加边

begin
    inc(num);
    edge[num].t := y;
    edge[num].next := head[x];
    edge[num].dis := z;
    head[x] := num;
end;

procedure kruskal;
var
    i:longint;

begin
    for i := 1 to n do f[i] := i;
    for i := 1 to m do
        if get(x[i]) <> get(y[i]) then
        begin
            f[get(x[i])] := get(y[i]);
            add(x[i],y[i],z[i]); add(y[i],x[i],z[i]);//加边
        end;
end;

procedure dfs(u,pre:longint);
var
    i,e:longint;

begin
    vis[u] := true;
    d[u] := d[pre] + 1;//深度+1
    fa[u][0] := pre;//父亲
    i := 0;
    while fa[u][i] <> 0 do
    begin
        w[u][i+1] := min(w[u][i],w[fa[u][i]][i]);
        fa[u][i+1] := fa[fa[u][i]][i];
        inc(i);
    end;
    i := head[u];
    while i <> 0 do
    begin
        e := edge[i].t;
        if not vis[e] and (e <> pre) then//访问没访问过的点
        begin
            w[e][0] := edge[i].dis;
            dfs(e,u);
        end;
        i := edge[i].next;
    end;
end;

function lca(u,v:longint):longint;
var
    i:longint;

begin
    if get(u) <> get(v) then exit(-1);//-1的情况
    lca := maxlongint;
    if d[u] > d[v] then swap(u,v);
    for i := 20 downto 0 do
        if d[u] <= d[v] - (1 << i) then
        begin
            lca := min(lca,w[v][i]);
            v := fa[v][i];
        end;
    if u = v then exit(lca);
    for i := 20 downto 0 do
        if fa[u][i] <> fa[v][i] then
        begin
            lca := min(lca,min(w[u][i],w[v][i]));
            u := fa[u][i]; v := fa[v][i];
        end;
    lca := min(lca,min(w[u][0],w[v][0]));
end;

begin
    readln(n,m);
    for i := 1 to m do readln(x[i],y[i],z[i]);
    sort(1,m);
    kruskal;
    for i := 1 to n do
        if not vis[i] then
        begin
            w[i][0] := maxlongint;
            dfs(i,0);
        end;
    readln(q);
    for i := 1 to q do
    begin
        readln(xx,yy);
        writeln(lca(xx,yy));
    end;
end.