TyvjP1135 [NOI2009] 植物大战僵尸 — 最大流/最小割/最大权闭合子图

Note: 本文最初于 2011年02月06日 星期日 19:36 在 hi.baidu.com/lydrainbowcat 发表。šš

算法思想概述

本题是一道最大权闭合子图模型，应用的算法为最大流(BFS增广即可)，定理为最大流最小割定理，辅助算法为拓扑排序。

问题初始建模

首先我们我建立图论模型，把每个植物当做一个顶点，植物携带的资源数目为顶点的权值。如果一个植物b在另一个植物a的攻击范围内，连接一条有向边<a,b>，表示a可以保护b。由于僵尸从右向左进攻，可以认为每个植物都被它右边相邻的植物保护，对于每个植物a（除最左边一列），向其左边的相邻植物b，连接一条有向边<a,b>。

由本题样例就可以发现，有一些植物是相互依赖的，于是我们可以进行算法实现的第一步：

  1.使用拓扑排序去除图中的环，从而使图得到简化。

最大权闭合子图

进行算法的第二步。

   2.对第一步中得到的图进行转置操作(把所有边反向)，从而得到最大子权闭合图。

样例的图经过拓扑排序和转置操作后如下：

    其中最大权闭合子图为(1,2,4) 

下面进行算法实现的第3、4步：

   3.最大权闭合子图的网络流建模：

(1). 建立附加源S和附加汇T。

(2). 图中原有的转置后的边容量设为∞。

(3). 从S向每个权值为正的点连接一条容量为该点权值的有向边。

(4). 从每个权值不为正的点向T连接一条容量为该点权值绝对值的有向边。

   建模后图如下：

   4.求解：求S到T的最大流Maxflow，最大权闭合子图的权值就是(所有正权点权值之和 – Maxflow)，也就是需要输出的答案。

算法证明及复杂度分析

对于最大流最小割的详解，参见黑书《算法艺术与信息学竞赛》网络流部分第二道例题航天计划。

对于最大权闭合子图建图方法正确性的证明，参见胡伯涛《最小割模型在信息学竞赛中的应用》。

另有更为简便的、使用二元关系与最小割方程模型来证明的方法，博主在讲课的课件中曾多次提及，也可参见彭天翼《浅析一类最小割问题》。

参考程序

var
 a,f:array[0..601,0..601]of longint;
 d,score,link,incf,q:array[0..1000]of longint;
 yes,vis:array[0..601]of boolean;
 n,m,s,t,i,j,u,v,k,x,y,tot:longint;
procedure topsort;//因为数据不大，写了个朴素的拓扑排序，没用栈和队列
 var
  com:boolean;
  i,j:longint;
 begin
  com:=false;
  while not com do
   begin
    com:=true;
    for i:=1 to n*m do
     if d[i]=0 then
      begin
       dec(d[i]);
       yes[i]:=true;
       for j:=1 to a[i,0] do dec(d[a[i,j]]);
       com:=false;
      end;
   end;
 end;
function maxflow:longint;
 function min(x,y:longint):longint;
  begin
   if x<y then exit(x) else exit(y);
  end;
 function bfs:boolean;
  var
   l,r,i,u,v:longint;
  begin
   fillchar(q,sizeof(q),0);
   fillchar(vis,sizeof(vis),0);
   l:=1; r:=1;
   q[1]:=s; vis[s]:=true;
   link[s]:=s; incf[s]:=maxlongint;
   while l<=r do
    begin
     u:=q[l];
     for i:=1 to n*m+1 do
      if not vis[i] and(f[u,i]>0) then
       begin
        vis[i]:=true;
        inc(r);
        q[r]:=i;
        link[i]:=u;
        incf[i]:=min(incf[u],f[u,i]);
        if i=t then exit(true);
       end;
     inc(l);
    end;
   exit(false);
  end;
 procedure update;
  var
   u,v:longint;
  begin
   u:=t;
   while u<>s do
    begin
     v:=u;
     u:=link[v];
     dec(f[u,v],incf[t]);
     inc(f[v,u],incf[t]);
    end;
   inc(maxflow,incf[t]);
  end;
 begin
  maxflow:=0;
  while bfs do update;
 end;
begin
 readln(n,m);
 s:=0; t:=n*m+1;
 for i:=1 to n do
  for j:=1 to m do
   begin
    u:=(i-1)*m+j;
    read(score[u]);
    read(a[u,0]);
    for k:=1 to a[u,0] do
     begin
      read(x,y);
      v:=x*m+y+1;
      a[u,k]:=v;
      inc(d[v]);
     end;
   end;
 for i:=1 to n do
  for j:=1 to m-1 do
   begin
    u:=(i-1)*m+j+1;
    v:=(i-1)*m+j;
    inc(a[u,0]);
    a[u,a[u,0]]:=v;
    inc(d[v]);
   end;
 topsort;
 for i:=1 to n*m do
  if yes[i] then
   begin
    if score[i]>=0 then
     begin inc(tot,score[i]); f[s,i]:=score[i] end
    else f[i,t]:=abs(score[i]);
    for j:=1 to a[i,0] do
     if yes[a[i,j]] then f[a[i,j],i]:=maxlongint;
   end;
 writeln(tot-maxflow);
end.