Program Poj_2112;//by whitetooth;
Const
    maxn=250;maxm=15000;
    filename='milking';
Var
    pre,other,flow              :array[0..maxm] of longint;
    last,can,dist,sum,father    :array[0..maxn] of longint;
    a                           :array[0..maxn,0..maxn] of longint;
    n,m,c,i,s,t,ans             :longint;
    
Procedure Init;
Var
    j                           :longint;
Begin
    read(n,m,c);
    
    s:=0;t:=n+m+1;
    fillchar(a,sizeof(a),100);
    
    for i:=1 to n+m do
        for j:=1 to n+m do
            begin
                read(a[i,j]);
                if (a[i,j]=0)and(i<>j) then a[i,j]:=maxlongint shr 1;
            end;
End;
    
Procedure Prepare;
Var
    j,k                         :longint;
Begin
    for k:=1 to n+m do
        for i:=1 to n+m do
            for j:=1 to n+m do 
                if a[i,j]>a[i,k]+a[k,j] then a[i,j]:=a[i,k]+a[k,j];
End;
    
Procedure In_Path(Var l:longint;p,q,r:longint);
Begin
    inc(l);pre[l]:=last[p];last[p]:=l;other[l]:=q;flow[l]:=r;
    inc(l);pre[l]:=last[q];last[q]:=l;other[l]:=p;flow[l]:=0;
End;
    
Function Max_flow:longint;
Var
    p,q,inflow,k,min            :longint;
    flag                        :boolean;
Begin
    max_flow:=0;
    for i:=s to t do can[i]:=last[i];
    sum[0]:=t+1;
    i:=s;
    inflow:=maxlongint;
    
    while dist[s]<t+1 do
        begin
            flag:=false;
            
            p:=can[i];
            while p<>-1 do
                begin
                    q:=other[p];
                    if (flow[p]>0)and(dist[i]=dist[q]+1) then
                        begin
                            flag:=true;
                            
                            if flow[p]<inflow then inflow:=flow[p];
                            
                            can[i]:=p;
                            father[q]:=p;
                            i:=q;
                            
                            if i=t then
                                begin
                                    inc(max_flow,inflow);
                                    while i<>s do
                                        begin
                                            p:=father[i];
                                            dec(flow[p],inflow);
                                            inc(flow[p xor 1],inflow);
                                            i:=other[p xor 1];
                                        end;
                                    inflow:=maxlongint;
                                end;
                                
                            break;
                        end;
                    p:=pre[p];
                end;
                
            if flag then continue;
            
            min:=t+1;
            p:=last[i];
            while p<>-1 do
                begin
                    q:=other[p];
                    if (flow[p]>0)and(dist[q]<min) then
                        begin
                            min:=dist[q];
                            k:=p;
                        end;
                    p:=pre[p];
                end;
            can[i]:=k;
            
            dec(sum[dist[i]]);
            if sum[dist[i]]=0 then break;
            dist[i]:=min+1;
            inc(sum[dist[i]]);
            
            if i<>s then i:=other[father[i] xor 1];
        end;
End;
    
Function Check(x:longint):boolean;
Var
    i,j,l,temp                  :longint;
Begin
    fillchar(last,sizeof(last),255);
    fillchar(dist,sizeof(dist),0);
    fillchar(sum,sizeof(sum),0);
    l:=-1;
    
    for i:=1 to n do
        for j:=n+1 to n+m do
            if a[i,j]<=x then in_path(l,i,j,1);
            
    for i:=1 to n do in_path(l,s,i,c);
    for i:=n+1 to n+m do in_path(l,i,t,1);
    
    temp:=max_flow;
    
    if temp=m then exit(true)
    else exit(false);
End;
    
Procedure Main;
Var
    j,l,r,mid,max               :longint;
Begin
    prepare;
    
    max:=0;
    for i:=1 to n do
        for j:=n+1 to n+m do
            if a[i,j]>max then max:=a[i,j];
    
    l:=0;r:=max;
    while l<=r do
        begin
            mid:=(l+r) shr 1;
            if check(mid) then
                begin
                    ans:=mid;
                    r:=mid-1;
                end
            else l:=mid+1;
        end;
End;
    
Procedure Print;
Begin
    writeln(ans);
End;
    
Begin
    Init;
    Main;
    Print;
End.

USACO的数据全都过了，交到这里就是WA……

• 求数据 (0) 896295334 2017-09-26 16:11:55