bzoj 1834

灰太狼 2021-12-20 14:51 215阅读 0赞

网络流的模板题

首先第一问我们直接用dinic搞就行了，费用直接存为0（时间上界非常松，这道题是能过），然后第二问我们只需要在第一问

的残余网络上加一个源点，源点指向1号点，容量为k，费用为0，然后对于之前的每一条边，建一个相同的边

容量为无穷大，费用为原来的费用。

//By BLADEVIL
    var
        pre, other, len, w            :array[0..20100] of longint;
        last                        :array[0..2100] of longint;
        l                            :longint;
        n, m, k                     :longint;
        father, que, dis            :array[0..2100] of longint;
        flag                        :array[0..2100] of boolean;
        a, b, c, d                    :array[0..20100] of longint;
        cost                        :longint;
        
    function min(a,b:longint):longint;
    begin
        if a>b then min:=b else min:=a;
    end;
        
    procedure connect(a,b,c,d:longint);
    begin
        inc(l);
        pre[l]:=last[a];
        last[a]:=l;
        other[l]:=b;
        len[l]:=c;
        w[l]:=d;
    end;
    
    procedure init;
    var
        i                            :longint;
        
    begin
        read(n,m,k);
        l:=1;
        for i:=1 to m do read(a[i],b[i],c[i],d[i]);
        for i:=1 to m do 
        begin
            connect(a[i],b[i],c[i],0);
            connect(b[i],a[i],0,0);
        end;
    end;
    
    function bfs:boolean;
    var
        q, p                        :longint;
        cur                            :longint;
        h, t                        :longint;
    begin
        fillchar(dis,sizeof(dis),0);
        h:=0; t:=1;
        que[1]:=1; dis[1]:=1;
        while t<>h do 
        begin
            inc(h);
            cur:=que[h];
            q:=last[cur];
            while q<>0 do 
            begin
                p:=other[q];
                if (len[q]>0) and (dis[p]=0) then 
                begin
                    inc(t);
                    que[t]:=p;
                    dis[p]:=dis[cur]+1;
                    if p=n then exit(true);
                end;
                q:=pre[q];
            end;
        end;
        exit(false);
    end;
    
    function dinic(x,flow:longint):longint;
    var
        q, p                        :longint;
        rest, tmp                    :longint;
    begin
        if x=n then exit(flow);
        rest:=flow;
        q:=last[x];
        while q<>0 do
        begin
            p:=other[q];
            if (len[q]>0) and (rest>0) and (dis[p]=dis[x]+1) then 
            begin
                tmp:=dinic(p,min(len[q],rest));
                dec(rest,tmp);
                dec(len[q],tmp);
                inc(len[q xor 1],tmp);
            end;
            q:=pre[q];
        end;
        exit(flow-rest);
    end;
    
    procedure spfa;
    var
        q, p                        :longint;
        h, t, cur                    :longint;
        
    begin
        fillchar(flag,sizeof(flag),false);
        filldword(dis,sizeof(dis) div 4,maxlongint div 10);
        h:=0; t:=1;
        que[1]:=n+1;
        dis[n+1]:=0;
        while h<>t do 
        begin
            h:=h mod 2000+1;
            cur:=que[h];
            flag[cur]:=false;
            q:=last[cur];
            while q<>0 do
            begin
                if len[q]>0 then 
                begin
                    p:=other[q];
                    if dis[cur]+w[q]<dis[p] then
                    begin
                        dis[p]:=dis[cur]+w[q];
                        father[p]:=q;
                        if not flag[p] then 
                        begin
                            t:=t mod 2000+1;
                            que[t]:=p;
                            flag[p]:=true;
                        end;
                    end;
                end;
                q:=pre[q];
            end;
        end;
    end;
    
    procedure update;
    var
        cur                            :longint;
        low                            :longint;
    begin
        cur:=n;
        low:=maxlongint div 10;
        while cur<>n+1 do 
        begin
            low:=min(low,len[father[cur]]);
            cur:=other[father[cur] xor 1];
        end;
        cur:=n;
        while cur<>n+1 do 
        begin
            inc(cost,low*w[father[cur]]);
            dec(len[father[cur]],low);
            inc(len[father[cur] xor 1],low);
            cur:=other[father[cur] xor 1];
        end;
    end;
        
    procedure main;
    var
        ans                            :longint;
        i                            :longint;
        
    begin
        ans:=0;
        while bfs do 
            ans:=ans+dinic(1,maxlongint div 10);
    
        for i:=1 to m do 
        begin
            connect(a[i],b[i],maxlongint div 10,d[i]);
            connect(b[i],a[i],0,-d[i]);
        end;
        
        connect(n+1,1,k,0);
        connect(1,n+1,0,0);
        while true do
        begin
            spfa;
            if dis[n]=maxlongint div 10 then break;
            update;
        end;
        writeln(ans,' ',cost);
    end;
    
    begin
        init;
        main;
    end.

转载于:https://www.cnblogs.com/BLADEVIL/p/3442589.html