bzoj1412

比较裸的最小割
注意狼和羊的领地可以通过空地相连
  1 const inf=100000007;
  2       dx:array[1..4] of integer=(0,0,1,-1);
  3       dy:array[1..4] of integer=(-1,1,0,0);
  4 
  5 type node=record
  6        next,point,flow:longint;
  7      end;
  8 
  9 var edge:array[0..200010] of node;
 10     a,num:array[0..110,0..110] of longint;
 11     p,cur,h,numh,pre:array[0..10010] of longint;
 12     n,m,x,y,len,i,j,t,k:longint;
 13 
 14 function min(a,b:longint):longint;
 15   begin
 16     if a>b then exit(b) else exit(a);
 17   end;
 18 
 19 procedure add(x,y,f:longint);
 20   begin
 21     inc(len);
 22     edge[len].point:=y;
 23     edge[len].flow:=f;
 24     edge[len].next:=p[x];
 25     p[x]:=len;
 26   end;
 27 
 28 function sap:longint;
 29   var s,u,i,j,neck,q,tmp:longint;
 30   begin
 31     u:=0;
 32     numh[0]:=t+1;
 33     sap:=0;
 34     while h[0]<t+1 do
 35     begin
 36       if u=t then
 37       begin
 38         i:=0;
 39         neck:=inf;
 40         while i<>t do
 41         begin
 42           j:=cur[i];
 43           if neck>edge[j].flow then
 44           begin
 45             neck:=edge[j].flow;
 46             s:=i;
 47           end;
 48           i:=edge[j].point;
 49         end;
 50         i:=0;
 51         while i<>t do
 52         begin
 53           j:=cur[i];
 54           dec(edge[j].flow,neck);
 55           inc(edge[j xor 1].flow,neck);
 56           i:=edge[j].point;
 57         end;
 58         u:=s;
 59         sap:=sap+neck;
 60       end;
 61       q:=-1;
 62       i:=p[u];
 63       while i<>-1 do
 64       begin
 65         j:=edge[i].point;
 66         if (edge[i].flow>0) and (h[u]=h[j]+1) then
 67         begin
 68           q:=i;
 69           break;
 70         end;
 71         i:=edge[i].next;
 72       end;
 73       if q<>-1 then
 74       begin
 75         cur[u]:=q;
 76         pre[j]:=u;
 77         u:=j;
 78       end
 79       else begin
 80         dec(numh[h[u]]);
 81         if numh[h[u]]=0 then exit;
 82         tmp:=t+1;
 83         i:=p[u];
 84         while i<>-1 do
 85         begin
 86           j:=edge[i].point;
 87           if edge[i].flow>0 then tmp:=min(tmp,h[j]);
 88           i:=edge[i].next;
 89         end;
 90         h[u]:=tmp+1;
 91         inc(numh[h[u]]);
 92         if u<>0 then u:=pre[u];
 93       end;
 94     end;
 95   end;
 96 
 97 begin
 98   len:=-1;
 99   fillchar(p,sizeof(p),255);
100   readln(n,m);
101   for i:=1 to n do
102     for j:=1 to m do
103     begin
104       read(a[i,j]);
105       inc(t);
106       num[i,j]:=t;
107     end;
108   inc(t);
109   for i:=1 to n do
110     for j:=1 to m do
111     begin
112       if a[i,j]=1 then
113       begin
114         add(0,num[i,j],inf);
115         add(num[i,j],0,0);
116       end
117       else if a[i,j]=2 then
118       begin
119         add(num[i,j],t,inf);
120         add(t,num[i,j],0);
121       end;
122       for k:=1 to 4 do
123       begin
124         x:=i+dx[k];
125         y:=j+dy[k];
126         if (x>0) and (x<=n) and (y>0) and (y<=m) then
127         begin
128           if (a[i,j]=1) and (a[x,y]<>1) then
129           begin
130             add(num[i,j],num[x,y],1);
131             add(num[x,y],num[i,j],0);
132           end
133           else if (a[i,j]=0) then
134           begin
135             add(num[i,j],num[x,y],1);
136             add(num[x,y],num[i,j],0);
137           end;
138         end;
139       end;
140     end;
141   writeln(sap);
142 end.
View Code