bzoj1412 狼和羊的故事【网络流最小割】
http://www.lydsy.com/JudgeOnline/problem.php?id=1412
题目大意就是将0分成1和2,然后在格子的边界建篱笆,将所有的1和2隔开,注意所有的0都要分成1和2。
解法就是用最小割的思想解决。
首先先建图:
对于每个a[i,j]=1,从s连到a[i,j]一条容量为正无穷的边。
对于每个a[i,j]=2,从a[i,j]连到t一条容量为正无穷的边。
对于相邻的两个格子a[i,j]和a[x,y],连一条a[i,j]和a[x,y]的容量为1的双向边。
那么最小割就是解。
接下来是证明:
为了把1和2隔开,就相当于把两种数字分别分到s割和t割,因为有容量为正无穷的边,所以可以保证所有的1都在s割,所有的2都在t割。
接下来就是解决0的问题。
0可以当作1或者2,如果a[i,j]和a[x,y]一个是0一个是1(或2),如果把这条边割掉,说明就将a[i,j]分到a[x,y]的对面。如果a[i,j]和a[x,y]一个是1一个是2,那么就必须把这条边割掉。如果a[i,j]和a[x,y]都是1或者都是2,那么就不需要割掉,建图时可以不建这条边,当然为了写的方便也可以加上,反正不影响答案。
代码:
const maxe=120000; maxn=10005; type edge=record x,y,next,op:longint; end; var e:array[0..maxe]of edge; map:array[1..100,1..100]of longint; a,gap,dis,pre,cur:array[0..maxn]of longint; n,m,i,j,k,s,t,u,v,cap,flow,mf:longint; procedure adde(u,v,cap,cc:longint); begin inc(k); e[k].y:=cap; e[k].x:=v; e[k].next:=a[u]; e[k].op:=k+1; a[u]:=k; inc(k); e[k].y:=cc; e[k].x:=u; e[k].op:=k-1; e[k].next:=a[v]; a[v]:=k; end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure sap; var i,j,k,now,p,pp,dist:longint; f:boolean; begin fillchar(dis,sizeof(dis),0); fillchar(gap,sizeof(gap),0); for i:=s to t do cur[i]:=a[i]; mf:=0; now:=s; gap[t]:=t; flow:=2147483647; while dis[s]<=t do begin if now=t then begin flow:=2147483647; i:=s; while i<>t do begin flow:=min(flow,e[cur[i]].y); i:=e[cur[i]].x; end; i:=s; while i<>t do begin dec(e[cur[i]].y,flow); inc(e[e[cur[i]].op].y,flow); i:=e[cur[i]].x; end; mf:=mf+flow; now:=s; end; p:=cur[now]; f:=true; while p<>0 do begin pp:=e[p].x; if (e[p].y>0) and (dis[now]=dis[pp]+1) then begin cur[now]:=p; pre[pp]:=now; now:=pp; f:=false; break; end; p:=e[p].next; end; if f then begin dec(gap[dis[now]]); if gap[dis[now]]=0 then break; cur[now]:=a[now]; p:=a[now]; dis[now]:=t+1; while p<>0 do begin pp:=e[p].x; if (e[p].y>0) then dis[now]:=min(dis[pp]+1,dis[now]); p:=e[p].next; end; inc(gap[dis[now]]); if now<>s then now:=pre[now]; end; end; end; begin //assign(input,'1.in'); //assign(output,'2.out'); //reset(input); //rewrite(output); read(n,m); for i:=1 to n do for j:=1 to m do read(map[i,j]); s:=0; t:=n*m+1; for i:=1 to n do for j:=1 to m do begin if map[i,j]=1 then adde(s,(i-1)*m+j,2147483647,0); if map[i,j]=2 then adde((i-1)*m+j,t,2147483647,0); if i<>1 then adde((i-1)*m+j,(i-2)*m+j,1,0); if j<>1 then adde((i-1)*m+j,(i-1)*m+j-1,1,0); if i<>n then adde((i-1)*m+j,i*m+j,1,0); if j<>m then adde((i-1)*m+j,(i-1)*m+j+1,1,0); end; sap; writeln(mf); //close(input); //close(output); end.</b>
PS:感谢zzx提供的sap模版!
PS2:当时调这题时真是困难重重,先是无论如何都A不了,然后找zzx的程序对拍,发现错误后死活不知道问题在哪,结果过了几天才发现其实是zzx的程序有一个小问题,最后找dwjed的程序,用随机生成的10*10数据拍了几分钟都没问题,最后发现忘了邻接表数组要开2倍。。。然后发现for j:=1 to m do打成了for j:=1 to n do。。。
PSP:无论如何,总算是A了这个第一道用SAP做的非模版题。。。
发表回复