bzoj1458

题做多的话不难想到可能是以行列作为二分图两个点集，然后网络流相关

具体怎么弄呢

我们可以用求补集的思想，假设有解

我们先把棋盘能放的地方放满士兵，然后我们尽量的把士兵拿走

并且要满足行和列的要求，

说到这方法就很明显了

ans=n*m-障碍数-最大流

我们用x[i]表示棋盘放满后第i行最多能移开的士兵数

y[i]表示棋盘放满后第i列最多能移开的士兵数

然后建图就更明显了，不多说

无解预先判断一下即可

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

View Code