本文共 2748 字，大约阅读时间需要 9 分钟。
1 /************************************************************** 2 Problem: 1475 3 User: HansBug 4 Language: Pascal 5 Result: Accepted 6 Time:304 ms 7 Memory:612 kb 8 ****************************************************************/ 9 10 type11 point=^node;12 node=record13 g,w:longint;14 anti,next:point;15 end;16 var17 i,j,k,l,m,n,s,t,flow:longint;18 a,e:array[0..10000] of point;19 b,c,d:array[0..10000] of longint;20 function min(x,y:longint):longint;21 begin22 if xnil do40 begin41 if (p^.w<>0) and (c[p^.g]=maxlongint) then42 begin43 e[p^.g]:=p;44 c[p^.g]:=c[d[f]]+1;45 d[r]:=p^.g;inc(r);46 end;47 p:=p^.next;48 end;49 inc(f);50 end;51 exit(c[t]<>maxlongint);52 end;53 procedure deal;54 begin55 i:=t;l:=maxlongint;56 while i<>s do57 begin58 l:=min(e[i]^.w,l);59 i:=e[i]^.anti^.g;60 end;61 dec(flow,l);i:=t;62 while i<>s do63 begin64 if e[i]^.w<>maxlongint then dec(e[i]^.w,l);65 if e[i]^.anti^.w<>maxlongint then inc(e[i]^.anti^.w,l);66 i:=e[i]^.anti^.g;67 end;68 end;69 begin70 readln(n);flow:=0;s:=1;t:=n*n+2;71 for i:=1 to n*n+2 do a[i]:=nil;72 for i:=1 to n do73 for j:=1 to n do74 begin75 read(k);inc(flow,k);76 if odd(i+j) then add(1,(i-1)*n+j+1,k) else add((i-1)*n+j+1,n*n+2,k);77 if odd(i+j) then78 begin79 if i>1 then add((i-1)*n+j+1,(i-2)*n+j+1,maxlongint);80 if i 1 then add((i-1)*n+j+1,(i-1)*n+j,maxlongint);82 if j
转载地址：http://jpezz.baihongyu.com/