jiry_2's Blog

类似于那道BZOJ1221软件开发，把每天拆成两个，分别记为Xi，Yi，从S向Yi连一条流量Ai，费用为0的边。从Yi向Yi+1连一条流量maxint。对于每一个医院从Yi向Xi+Dk+1连一条流量为maxint，费用为Qk的边。从Xi向T连一条流量为k，费用为0的边。再对于每个大学都建一个节点Mi，从Mi向X1连一条流量为maxint，费用为Pi的边，从S向Mi连一条流量为Li，费用为0的边。这个网络的最小费用最大流的费用就是答案。开始数组开太大，估计是fillchar花了太多时间就T了。后来把数组改小就A了。

program p3280;
    const
        maxn=1000000000;
		modd=100000;
    type
        bian=record
            next,point,w,f:longint;
        end;
    var
		ii,t,tt,i,j,n,m,k,len,totpoint,totflow,totw,totnum:longint;
        a,l,pp,q,d:array[1..10000] of longint;
        b:array[0..200000] of bian;
        p,after,dis:array[0..10000] of longint;
        x:array[1..100000] of longint;
        pd:array[0..10000] of boolean;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    procedure ade(k1,k2,k3,k4:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].next:=p[k1];
            b[len].f:=k3;
            b[len].w:=k4;
            p[k1]:=len;
        end;
    procedure add(k1,k2,k3,k4:longint);
        begin
            ade(k1,k2,k3,k4);
            ade(k2,k1,0,-k4);
        end;
    function spfa:boolean;
        var
            head,i,j,now:longint;
        begin
            fillchar(x,sizeof(x),0);
            fillchar(pd,sizeof(pd),false);
            fillchar(dis,sizeof(dis),$3f);
            fillchar(after,sizeof(after),-1);
            x[1]:=0; head:=1; now:=0; pd[0]:=true; dis[0]:=0;
            while head<>now do begin
                now:=now mod modd+1;
                i:=p[x[now]];
                while i<>-1 do begin
                    j:=b[i].point;
                    if (b[i].f>0) and (b[i].w+dis[x[now]]<dis[j]) then begin
                        dis[j]:=b[i].w+dis[x[now]];
                        after[j]:=i;
                        if pd[j]=false then begin
                            pd[j]:=true;
                            head:=head mod modd+1;
                            x[head]:=j;
                        end;
                    end;
                    i:=b[i].next;
                end;
                pd[x[now]]:=false;
            end;
            if after[totpoint]>-1 then exit(true) else exit(false);
        end;
    function change:longint;
        var
            k,ans,tot,num,i,j:longint;
        begin
            i:=totpoint; j:=after[i]; k:=maxn;
            while j<>-1 do begin
                k:=min(k,b[j].f);
                i:=b[j xor 1].point;
                j:=after[i];
            end;
            ans:=0; i:=totpoint; j:=after[i];
            while j<>-1 do begin
                ans:=ans+k*b[j].w;
                dec(b[j].f,k);
                inc(b[j xor 1].f,k);
                i:=b[j xor 1].point;
                j:=after[i];
            end;
            totflow:=totflow+k;
            exit(ans);
        end;
    function dinic:longint;
        var
            ans:longint;
        begin
            ans:=0;
            while spfa do
                ans:=ans+change;
            exit(ans);
        end;
    begin
        readln(t);
        for tt:=1 to t do begin
            totnum:=0;
            readln(n,m,k);
            len:=-1;
            fillchar(p,sizeof(p),-1);
            fillchar(b,sizeof(b),0);
            for i:=1 to n do begin
                read(a[i]);
                totnum:=totnum+a[i];
            end;
            for i:=1 to m do
                read(l[i],pp[i]);
            for i:=1 to k do
                read(d[i],q[i]);
			for i:=m+1 to m+n-1 do
				add(i,i+1,maxn,0);
            for i:=1 to m do begin
                add(0,i,l[i],0);
				add(i,m+1,maxn,pp[i]);
            end;
            for i:=1 to n do begin
                add(0,i+n+m,a[i],0);
                for j:=1 to k do
                    if i+d[j]+1<=n then
						add(i+n+m,m+i+d[j]+1,maxn,q[j]);
            end;
            totpoint:=n+n+m+1;
            for i:=1 to n do
                add(m+i,totpoint,a[i],0);
            totflow:=0;
            totw:=dinic;
            if totflow<totnum then
                writeln('Case ',tt,': impossible')
            else
                writeln('Case ',tt,': ',totw);
        end;
    end.