使用Dijkstra优化费用流 - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
NOI Linux 笔记
最小割的代价建模四题

使用Dijkstra优化费用流

Hoblovski posted @ 2014年7月14日 14:26 in Notes with tags dijkstra SPFA 笔记 费用流 , 940 阅读
费用流,OI中常见的做法是EKSPFA以及ZKW.蒟蒻一般使用ZKW,有负权用EKSPFA.
SPFA太慢了!费用流中我们是要反复求最短路,为什么每次都要SPFA?
于是我们可以使用Dijkstra来优化费用流.
 
前提
        任何时候残量子图中没有负环,残量子图即由G.E中容量c>0的边的导出子图.
 
Johnson算法
        对于有负权无负环的图的一种在O(VElgV)时间内的APSP算法
        算法步骤
                1.随便定一个顶点S,调用一次 Bellman Ford 计算出 h(u) = d(S,u)
                2.构造G',G'.V=G.V,任何(u,v,w) in G.E,(u,v,w+h[u]-h[v]) in G'.E
                3.在G'上跑V次Dijkstra,d(u,v) = d'(u,v)-h(u)+h(v)
        性质
                G'中权值非负,G'中最短路等价于G中最短路
                证明
                        1.权值非负 由三角不等式显然
                        2.最短路等价 易证对于任何路径P(u,v)
                                cost'(P(u,v)) = cost(P(u,v))+h(u)-h(v)
                由上也证明了任何使用顶标的重赋权都能保证最短路等价
 
算法
        类似Johnson算法维护结点顶标h(u)
        对于任何(u,v)保证h(u)+w(u,v)-h(v) >= 0,左边仍然是G'中(u,v)的权重
        初始化h(u) = 0,如果有负权则调用一次SPFA得到h(u) = d(S,u)
        每次增广后所有h(u) += d'(S,u),直到d'(S,T) = oo为止
        
        唯一的问题是每次增广后 h[u]+ = d'(S,u) 是否正确的,当然是.
        证明
                我们只需证明这样能保证任何(u,v),w'(u,v) >= 0
                        由三角不等式显然 d'(S,v) <=  d'(S,u)+w'(u,v)
                        ∴ d'(S,u)+w'(u,v)-d'(S,v) >= 0
                        ∵ w'(u,v) = w(u,v)+h(u)-h(v)
                        ∴ d'(S,u)+h(u) +w(u,v) +d'(S,v)+h(v) >=0
                        分别令h(u) += d'(S,u)新的顶标仍然性质被保持.
        
        由实践在正常情况下h(u)不会快速爆int.
 
优化
        堆Dijkstra太长了.
        来自Seter的意见,"使用ZKW线段树优化Dijkstra"
        使用ZKW线段树之后Dijkstra费用流23行(包含一行空行),如果是C++可以更短
        普通的EKSPFA有20行
        普通的ZKW有30行左右.
 
使用ZKW线段树优化的Dijkstra的费用流.能叫ZKW费用流么←_←
还有为什么用了Dijkstra反而我BZOJ3442更慢了,自己测都快如闪电(←_←~)
 
{$INLINE ON}
program Dijkstra_Optimised_Costflow;

type tnode=record
        n,c,w,next:longint;
     end;

const maxn=100017;
      maxm=1000017;
      maxint=longint($3f3f3f3f);

var g,h,d,q,pre,arc,dlt:array[0..maxn] of longint;
    t:array[0..maxn*4] of longint;
    v:array[0..maxn] of boolean;
    mem:array[0..maxm] of tnode;
    n,m,memsize,st,trm,flow,cost,zkw,frt,rer:longint;

function min(i,j:longint):longint; inline; begin if i<j then exit(i) else exit(j); end;

procedure insnbs(u,v,ic,iw:longint); inline;
begin
inc(memsize); with mem[memsize] do begin
        n:=v; c:=ic; w:=iw; next:=g[u];
end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin
        n:=u; c:=0; w:=-iw; next:=g[v];
end; g[v]:=memsize;
end;

procedure spfa;
var head,tail,t1:longint;
begin
fillchar(h,sizeof(h),$3f); h[st]:=0; frt:=0; rer:=1; q[1]:=st; v[st]:=true;
while frt<>rer do begin frt:=frt mod maxn+1; head:=q[frt];
        t1:=g[head]; while t1<>0 do begin tail:=mem[t1].n;
                if (mem[t1].c>0)and(h[tail]>h[head]+mem[t1].w) then begin
                        h[tail]:=h[head]+mem[t1].w; if not v[tail] then begin
                                rer:=rer mod maxn+1; q[rer]:=tail; v[tail]:=true;
                        end;
                end; t1:=mem[t1].next;
        end; v[head]:=false;
end;
end;

procedure edit(i,j:longint); inline;                                                    begin
inc(i,zkw); t[i]:=j; while i>1 do begin j:=i>>1; t[j]:=min(t[i],t[i xor 1]); i:=j; end; end;

procedure ek_dijkstra;
var i,j,k,u,w,t1:longint;
begin
zkw:=1; while zkw<n+2 do zkw:=zkw<<1; d[trm]:=0; flow:=0; cost:=0; while d[trm]<maxint do begin
        d[trm]:=maxint; fillchar(t,(zkw+1)<<3,$3f); fillchar(v,sizeof(v),0);
        edit(st,0); dlt[st]:=maxint; pre[st]:=0; for i:=1 to n do begin
                j:=1; while j<zkw do begin k:=j<<1; j:=k+byte(t[k xor 1]<t[k]); end;
                if t[j]=maxint then break; dec(j,zkw); d[j]:=t[j+zkw]; v[j]:=true; edit(j,maxint);
                t1:=g[j]; while t1<>0 do begin k:=mem[t1].n; w:=mem[t1].w+h[j]-h[k];
                        if (mem[t1].c>0)and(not v[k])and(t[k+zkw]>d[j]+w) then begin
                                pre[k]:=j; arc[k]:=t1; dlt[k]:=min(dlt[j],mem[t1].c); edit(k,d[j]+w);
                        end; t1:=mem[t1].next;
                end;
        end; if d[trm]-h[st]+h[trm]<maxint then begin
                u:=trm; w:=dlt[trm]; inc(flow,w); inc(cost,(d[trm]-h[st]+h[trm])*w);
                while u<>st do begin dec(mem[arc[u]].c,w); inc(mem[arc[u]xor 1].c,w); u:=pre[u]; end;
                for i:=1 to n do inc(h[i],d[i]);
        end else break;
end;
end;

procedure init;
var i,j,k,u,v,c,w:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1;
readln(n,m); for i:=1 to m do begin
        readln(u,v,c,w); insnbs(u,v,c,w);
end; st:=1; trm:=n;
end;

begin
init;
ek_dijkstra;
writeln(flow,' ',cost);
end.

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter