bzoj 1834-蒲公英云

bzoj 1834

灰太狼 2021-12-20 14:51 345阅读 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.