bzoj 2245 费用流

比较裸

源点连人，每个人连自己的工作，工作连汇，然后因为人的费用是

分度的，且是随工作数非降的，所以我们拆边，源点连到每个人s+1条边

容量是每段的件数，费用是愤怒

/**************************************************************
    Problem: 2245
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:1532 ms
    Memory:8048 kb
****************************************************************/
 
//By BLADEVIL
var
    n, m                                :longint;
    pre, other, len, cost               :array[0..500010] of longint;
    last                                :array[0..610] of longint;
    source, sink                        :longint;
    time                                :array[0..100] of longint;
    ans                                 :int64;
    father, dis, que                    :array[0..610] of longint;
    flag                                :array[0..610] of boolean;
    l                                   :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;
    cost[l]:=d;
end;
     
procedure init;
var
    i, j                                :longint;
    x, y                                :longint;
 
begin
    read(m,n);
    l:=1;
    source:=n+m+2; sink:=source+1;
    for i:=1 to n do
    begin
        read(x);
        connect(m+i,sink,x,0);
        connect(sink,m+i,0,0);
    end;
     
    for i:=1 to m do
        for j:=1 to n do
        begin
            read(x);
            if x=1 then
            begin
                connect(i,j+m,maxlongint div 10,0);
                connect(j+m,i,0,0);
            end;
        end;
     
    for i:=1 to m do
    begin
        read(x);
        for j:=1 to x do read(time[j]);
        time[0]:=0;
        time[x+1]:=maxlongint div 10;
        for j:=1 to x+1 do
        begin
            read(y);
            connect(source,i,time[j]-time[j-1],y);
            connect(i,source,0,-y);
        end;
    end;
end;
 
function spfa:boolean;
var
    h, t, cur                           :longint;
    q, p                                :longint;
begin
    filldword(dis,sizeof(dis) div 4,maxlongint div 10);
    h:=0; t:=1;
    que[1]:=source;
    dis[source]:=0;
    while h<>t do
    begin
        h:=h mod 600+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[p]>dis[cur]+cost[q] then
                begin
                    dis[p]:=dis[cur]+cost[q];
                    father[p]:=q;
                    if not flag[p] then
                    begin
                        t:=t mod 600+1;
                        que[t]:=p;
                        flag[p]:=true;
                    end;
                end;
            end;
            q:=pre[q];
        end;
    end;
    if dis[sink]=maxlongint div 10 then exit(false) else exit(true);
end;
 
procedure update;
var
    low                                 :longint;
    cur                                 :longint;
begin
    cur:=sink;
    low:=maxlongint;
    while cur<>source do
    begin
        low:=min(low,len[father[cur]]);
        cur:=other[father[cur] xor 1];
    end;
    cur:=sink;
    while cur<>source do
    begin
        dec(len[father[cur]],low);
        inc(len[father[cur] xor 1],low);
        ans:=ans+low*cost[father[cur]];
        cur:=other[father[cur] xor 1];
    end;
end;
 
procedure main;
begin
    while spfa do
        update;
    writeln(ans);
end;
 
begin
    init;
    main;
end.