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做的非模版题。。。

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.