bzoj1001: [BeiJing2006]狼抓兔子【最短路径】

  • 内容
  • 评论
  • 相关

题目点击这里


题目很好理解就是一道最小割的题目,但是俗话说得好,“看到100就要想到网络流”。然而这道题目N和M都是1000的,所以直接上最大流算法似乎是不太可行的。


这里就要充分利用这题里面的图的特点了。

可以发现,在这个图里面:

任意两条边都不会相交,这就是一个平面图,符合欧拉定理。

而且有一个源点S和汇点T,这就是一个ST平面图。

根据某神奇论文《浅析最大最小定理在信息学竞赛中的应用》,平面图可以转化成另一个平面图,也就是它的对偶图。对偶图有一些很神奇的性质,都在这篇论文里面,这里就不多说了。


根据上面的论文,一个ST平面图可以用一下办法转化为它的对偶图:

1、连接S和T,将外部的无限平面分成两部分,一个标为S一个标为T(具体哪个其实都一样的)。

2、平面图的每一个平面对应对偶图的每一个点,原图的一条边分开了哪两个平面就在对偶图中连接这两个平面的对应点。


建好对偶图后就可以用到它的性质:

对偶图中的任意一条路径会对应原图的一个割。

看上去有点莫名其妙,其实很好理解,严谨证明嘛,不知道意会一下啦。看了论文中的图还是很好理解的。


有了上面那条性质,我们就可以快速求出原图的最小割了,因为最短路径对应的割的总权值是相等的(建对偶图的时候边权不变)。

那么代码:

var
  dis,q,v,a,next,w:array[1..6000000]of longint;
  inq:array[1..6000000]of boolean;
  n,m,i,j,k,x,y,s,t,head,tail:longint;
procedure adde(uu,vv:longint);
begin
  inc(k);
  v[k]:=vv;
  next[k]:=a[uu];
  a[uu]:=k;
  w[k]:=x;
  inc(k);
  v[k]:=uu;
  next[k]:=a[vv];
  a[vv]:=k;
  w[k]:=x;
end;
begin
  read(n,m);
  s:=(n-1)*(m-1)*2+1;
  t:=s+1;
  for i:=1 to n do
  for j:=1 to m-1 do
  begin
    read(x);
    if i=1 then adde(((i-1)*(m-1)+j)*2,s)
    else if i=n then adde(((i-2)*(m-1)+j)*2-1,t)
    else adde(((i-2)*(m-1)+j)*2-1,((i-1)*(m-1)+j)*2);
  end;
  for i:=1 to n-1 do
  for j:=1 to m do
  begin
    read(x);
    if j=1 then adde(((i-1)*(m-1)+j)*2-1,t)
    else if j=m then adde(((i-1)*(m-1)+j-1)*2,s)
    else adde(((i-1)*(m-1)+j-1)*2,((i-1)*(m-1)+j)*2-1);
  end;
  for i:=1 to n-1 do
  for j:=1 to m-1 do
  begin
    read(x);
    adde(((i-1)*(m-1)+j)*2-1,((i-1)*(m-1)+j)*2);
  end;
  fillchar(inq,sizeof(inq),false);
  fillchar(dis,sizeof(dis),255);
  head:=0;
  tail:=1;
  q[1]:=s;
  dis[s]:=0;
  inq[s]:=true;
  repeat
    inc(head);
    if head>6000000 then head:=1;
    x:=q[head];
    i:=a[x];
    while i<>0 do
    begin
      y:=v[i];
      if (dis[y]=-1) or (dis[x]+w[i]<dis[y]) then
      begin
        dis[y]:=dis[x]+w[i];
        if not inq[y] then
        begin
          inq[y]:=true;
          inc(tail);
          if tail>6000000 then tail:=1;
          q[tail]:=y;
        end;
      end;
      i:=next[i];
    end;
    inq[x]:=false;
  until head=tail;;
  writeln(dis[t]);
end.

 

评论

0条评论

发表回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据