倍增算法学习ing

本题出自NOIP提高2013年的D1T3

题目描述

$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$。

数据规模

对于$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$。

题外话

这两天刚学习了如何用倍增算法来求LCA，于是便找来了这道题练习巩固一下，结果发现完全不会$QWQ$。

看完别的巨佬写的题解后，总算是有了思路。下面就来简单分析一下。

分析

废话不多说。不难看出有一些限重很小的边根本用不上，经过一番推敲，可以先用Kruscal求出图的的最大生成树再进行下一步处理。

最大生成树求出来后，两个节点间的的路径就确定下来了，可以直接暴力枚举找到该路径上边权(这里就是限重)的最小值，此值即为一个询问的答案。

但是看看数据规模，这种暴力枚举肯定没法$AC$，所以要提高找路径上的边权最小值的算法效率。这个时候就该倍增算法出场啦。。

实现

运用倍增法来求两个节点间边权的最小值，不妨设$fa[i,j]$为$i$节点向上跳$2^j$次后的节点序号，$w[i,j]$为$i$节点到$fa[i,j]$节点间路径权值的最小值。对于每一对点的询问，用倍增法找到该对点的最近公共祖先，在向上翻的过程中即可不断更新出该对点之间边权的最小值。最后需要注意整个图不一定联通，所以在求LCA前要用并查集来判定一下(正好在跑Kruscal时已经求出来了)。

代码

uses
math;
type
edge=record
from,too,v,next:longint;
end;
var
e,e2:array[1..100000] of edge;
head,dep,uset:array[0..10000] of longint;
flag:array[0..10000] of boolean;
fa,w:array[0..10000,0..20] of longint;
i,j,k,l,m,n,s,t,cnt,t1,t2,t3,q:longint;

procedure adde1(a,b,c:longint); begin inc(cnt); e[cnt].from:=a; e[cnt].too:=b; e[cnt].v:=c; end;
procedure adde2(a,b,c:longint); begin inc(cnt); e2[cnt].next:=head[a]; e2[cnt].too:=b; e2[cnt].v:=c; head[a]:=cnt; end;

procedure kp(l,r:longint);
var i,j,m:longint; t:edge;
begin
    i:=l; j:=r; m:=e[(l+r) shr 1].v;
    repeat
        while e[i].v>m do inc(i);
        while e[j].v<m do dec(j);
        if i<=j then
        begin
            t:=e[i]; e[i]:=e[j]; e[j]:=t;
            inc(i); dec(j);
        end;
    until i>j;
    if l<j then kp(l,j);
    if i<r then kp(i,r);
end;

function find(x:longint):longint;
begin if x=uset[x] then exit(x); uset[x]:=find(uset[x]); exit(uset[x]); end;

procedure dfs(x:longint);
var i,u:longint;
begin
    flag[x]:=true;
    i:=head[x];
    while i>0 do
    begin
        u:=e2[i].too;
        if flag[u] then begin i:=e2[i].next; continue; end;
        dep[u]:=dep[x]+1;
        fa[u,0]:=x;
        w[u,0]:=e2[i].v;
        dfs(u);
        i:=e2[i].next;
    end;
end;

function lca(a,b:longint):longint;
var i,t:longint;
begin
    if find(a)<>find(b) then exit(-1);
    if dep[a]<dep[b] then begin t:=a; a:=b; b:=t; end;
    lca:=maxlongint;
    for i:=20 downto 0 do
        if dep[fa[a,i]]>=dep[b] then begin lca:=min(lca,w[a,i]); a:=fa[a,i]; end;
    if a=b then exit(lca);
    for i:=20 downto 0 do
        if fa[a,i]<>fa[b,i] then begin lca:=min(lca,min(w[a,i],w[b,i])); a:=fa[a,i]; b:=fa[b,i]; end;
    lca:=min(lca,min(w[a,0],w[b,0]));
    exit(lca);
end;

begin
    readln(n,m); cnt:=0;
    for i:=1 to m do
    begin
        readln(t1,t2,t3);
        adde1(t1,t2,t3);
    end;
    
    kp(1,m); cnt:=0;
    for i:=1 to n do uset[i]:=i;
    k:=0;
    for i:=1 to m do
    begin
        t1:=find(e[i].from); t2:=find(e[i].too);
        if t1<>t2 then begin uset[t1]:=t2; adde2(e[i].from,e[i].too,e[i].v); adde2(e[i].too,e[i].from,e[i].v); inc(k); end;
        if k=n-1 then break;
    end;
    
    for i:=1 to n do
        if not flag[i] then
        begin
            dep[i]:=1; dfs(i); fa[i,0]:=i; w[i,0]:=maxlongint;
        end;
    
    for i:=1 to 20 do
        for j:=1 to n do
        begin
            fa[j,i]:=fa[fa[j,i-1],i-1];
            w[j,i]:=min(w[j,i-1],w[fa[j,i-1],i-1]);
        end;
    
    readln(q);
    for i:=1 to q do
    begin
        readln(t1,t2);
        writeln(lca(t1,t2));
    end;
end.

总结

本题还可以用数链剖分+线段树来解决，但我不会但是这毕竟已经超出了$NOIP$的范围，所以这里就不再展开啦。 个人认为本题对加深倍增法的理解有很大的作用和价值，倍增是一种对暴力很好的优化，而且容易理解，代码好写，运用广泛，非常值得学习$Orz$~~