动态最小生成树讲解

浏览数：16 / 时间：2015年06月09日

　　动态最小生成树是一类要求给定图，对于图的边有删除，插入，修改边权操作，满足查询MST（Minimum Spanning Tree ）的问题。

　　在这里我们考虑修改边的操作，删除可以看成是将边权设成INF，插入可以看做是将一条INF的边边权赋值。

　　那么假设我们有q个询问，每个询问修改一条边的权值。

　　对于q个询问里修改的边，我们设这个边集为Q，全集为E，那么对于E-Q中的边，做一遍MST，MST中的边集设为G，那么对于E-Q-G中的边，不论询问怎么改变，这些边都不会在MST中，所以我们可以删除这些边，这时全集E不包括刚才删除的边，全集中的边的数量变成了n+q，n为MST中必要的边，q为询问中的边。之后将Q中的边的边权都赋值为-ING，这时做一遍MST，如果E-Q的边在MST中，这时代表就算修改的边最小时这些边也要选，也就是这些边是保证MST连通性的必要的边，这些边我们也没有必要考虑，因为必须要选，所以将这条边连接的两个点合并成一个点，可以用并查集维护。那么这些操作之后，我们将边的规模变成了q的，点的规模变成了q的。那么我求出来询问包括1-q的情况了，在剩下的这张图（规模变小了）上，将询问的范围变成1-q>>1和q<<1-q，再递归的做下去，因为询问的不断地变小，每次都会有更多的边被缩掉（在第二次做MST时可以缩掉的边），每次边的规模都变成了q/2^dep，这样一共会有log₂q层，每层做MST是qlog₂q的，那么总的时间复杂度就是q(log₂q，我们递归的时候不用每次都排序，可以保存原来有序的边集，所以可以去掉一个log₂q，这样时间复杂度就变成了qlog₂q。

　　练习题，bzoj 2001 http://61.187.179.132/JudgeOnline/problem.php?id=2001

/**************************************************************
    Problem: 2001
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:14456 ms
    Memory:37024 kb
****************************************************************/
 
//By BLADEVIL
type
    node                            =record
    cnt                             :longint;
    a,b                             :array[1..250000]of longint;
    end;
     
var
    e                               :array[1..18] of node;
    fa                              :array[1..20000]of longint;
    x, y, data, tdata               :array[0..50000]of longint;
    num, cha, ord, opt              :array[0..50000]of longint;
    i , n, m, q                     :longint;
    ans                             :int64;
     
procedure swap(var a,b:longint);
var
    t                               :longint;
begin
    t:=a;
    a:=b;
    b:=t;
end;
 
procedure qsort(left,right:longint);
var
    i, j, bj                        :longint;
begin
    i:=left;
    j:=right;
    bj:=data[ord[(i+j) shr 1]];
    while i<=j do
    begin
        while data[ord[i]]<bj do inc(i);
        while data[ord[j]]>bj do dec(j);
        if i<=j then
        begin
            swap(ord[i],ord[j]);
            inc(i); dec(j);
        end;
    end;
    if j>left then qsort(left,j);
    if i<right then qsort(i,right);
end;
 
procedure work(dep,left,right:longint);
var
    i, tm, tcnt                     :longint;
    tans                            :int64;
 
function getfather(a:longint):longint;
var
    tmp                             :longint;
begin
    if fa[a]=a then exit(a);
    tmp:=a;
    while fa[tmp]<>tmp do tmp:=fa[tmp];
    while fa[a]<>tmp do
    begin
        inc(e[dep].cnt);
        e[dep].a[e[dep].cnt]:=a;
        e[dep].b[e[dep].cnt]:=fa[a];
        fa[a]:=tmp;
        a:=e[dep].b[e[dep].cnt];
    end;
    exit(tmp);
end;
 
procedure combine(a,b:longint);
begin
    a:=getfather(a);
    b:=getfather(b);
    inc(e[dep].cnt);
    e[dep].a[e[dep].cnt]:=a;
    e[dep].b[e[dep].cnt]:=fa[a];
    fa[a]:=b;
end;
 
procedure recover(a:longint);
begin
    while e[dep].cnt<>a do
    begin
        fa[e[dep].a[e[dep].cnt]]:=e[dep].b[e[dep].cnt];
        dec(e[dep].cnt);
    end;
end;
 
begin
    tans:=ans;
    e[dep].cnt:=0;
    if left=right then
    begin
        data[num[left]]:=cha[left];
        tdata[num[left]]:=cha[left];
        qsort(1,m);
        for i:=1 to m do
        if getfather(x[ord[i]])<>getfather(y[ord[i]]) then
        begin
            combine(x[ord[i]],y[ord[i]]);
            ans:=ans+data[ord[i]];
        end;
        writeln(ans);
        recover(0);
        ans:=tans;
        exit;
    end;
    tm:=m;
    for i:=left to right do
        data[num[i]]:=-maxlongint;
    qsort(1,m);
    opt[0]:=0;
    for i:=1 to m do
        if getfather(x[ord[i]])<>getfather(y[ord[i]]) then
        begin
            combine(x[ord[i]],y[ord[i]]);
            if data[ord[i]]<>-maxlongint then
            begin
                inc(opt[0]);
                opt[opt[0]]:=ord[i];
            end;
        end;
    recover(0);
    for i:=1 to opt[0] do
    begin
        combine(x[opt[i]],y[opt[i]]);
        ans:=ans+data[opt[i]];
    end;
    tcnt:=e[dep].cnt;
    for i:=left to right do
        data[num[i]]:=maxlongint;
    qsort(1,m);
    opt[0]:=0;
    for i:=1 to m do
        if getfather(x[ord[i]])<>getfather(y[ord[i]]) then
            combine(x[ord[i]],y[ord[i]]) else
                if data[ord[i]]<>maxlongint then
                begin
                    inc(opt[0]);
                    opt[opt[0]]:=i;
                end;
    for i:=opt[0] downto 1 do
    begin
        swap(ord[opt[i]],ord[m]);
        dec(m);
    end;
    recover(tcnt);
    for i:=left to right do
        data[num[i]]:=tdata[num[i]];
    work(dep+1,left,(left+right) shr 1);
    work(dep+1,(left+right) shr 1 +1,right);
    m:=tm;
    ans:=tans;
    recover(0);
end;
 
begin
    readln(n,m,q);
    for i:=1 to n do
        fa[i]:=i;
    for i:=1 to m do
    begin
        readln(x[i],y[i],data[i]);
        tdata[i]:=data[i];
        ord[i]:=i;
    end;
    for i:=1 to q do
        readln(num[i],cha[i]);
    work(1,1,q);
end.