1565: [NOI2009]植物大战僵尸

Description

Input

Output
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。
Sample Input
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0
Sample Output
25
HINT

在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。
一个方案为，首先进攻P1,1, P0,1，此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。
【大致数据规模】
约20%的数据满足1 ≤ N, M ≤ 5；
约40%的数据满足1 ≤ N, M ≤ 10；
约100%的数据满足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000 。

详情请见胡伯涛《最小割模型在信息学竞赛中的应用》中最大权闭合图

但是有一点不同，因为有些点不能取，所以我们首先拓扑一下，把有用的点选出来，然后再跑最小割

 const

     maxn=;

     maxm=;

     inf=;

 var

     d,a,first,q:array[..maxn*maxm]of longint;

     next,last:array[..maxn*maxm*maxn*maxm]of longint;

     map:array[..maxn*maxm,..maxn*maxm]of longint;

     n,m,tot,sum,cnt:longint;

 function calc(i,j:longint):longint;

 begin

     exit(i*m+j+);

 end;

 procedure insert(x,y:longint);

 begin

     inc(tot);

     last[tot]:=y;

     next[tot]:=first[x];

     first[x]:=tot;

     inc(d[y]);

 end;

 procedure init;

 var

     i,j,k,l,r,x,y:longint;

 begin

     read(n,m);

     for i:= to n- do

         for j:= to m- do

             begin

                 read(a[calc(i,j)]);

                 read(k);

                 if j> then insert(calc(i,j),calc(i,j-));

                 for l:= to k do

                     begin

                         read(x,y);

                         insert(calc(i,j),calc(x,y));

                     end;

             end;

     l:=;r:=;

     for i:= to n -1do

         if d[calc(i,m-)]= then

         begin

             inc(r);

             q[r]:=calc(i,m-);

         end;

     while l<=r do

         begin

             if a[q[l]]> then inc(sum,a[q[l]]);

             if a[q[l]]> then inc(map[,q[l]],a[q[l]]);

             if a[q[l]]< then inc(map[q[l],n*m+],-a[q[l]]);

             i:=first[q[l]];

             while i<> do

                 begin

                     dec(d[last[i]]);inc(map[last[i],q[l]],inf);

                     if d[last[i]]= then

                     begin

                         inc(r);

                         q[r]:=last[i];

                     end;

                     i:=next[i];

                 end;

             inc(l);

         end;

     cnt:=r;

 end;

 var

     dis,vh,his,pre:array[..maxn*maxm]of longint;

     flow:longint;

 procedure sap;

 var

     i,j,aug,min:longint;

     flag:boolean;

 begin

     vh[]:=cnt+;

     i:=;aug:=inf;

     while dis[i]<n*m+ do

         begin

             his[i]:=aug;

             flag:=false;

             for j:= to n*m+ do

                 if (map[i,j]>) and (dis[i]=dis[j]+) then

                 begin

                     flag:=true;

                     if aug>map[i,j] then aug:=map[i,j];

                     pre[j]:=i;

                     i:=j;

                     if i=n*m+ then

                     begin

                         inc(flow,aug);

                         while i<> do

                             begin

                                 inc(map[i,pre[i]],aug);

                                 dec(map[pre[i],i],aug);

                                 i:=pre[i];

                             end;

                         aug:=inf;

                     end;

                     break;

                 end;

             if flag then continue;

             min:=n*m+;

             for j:= to n*m+ do

                 if (map[i,j]>) and (dis[j]<min) then min:=dis[j];

             dec(vh[dis[i]]);

             if vh[dis[i]]= then break;

             dis[i]:=min+;

             inc(vh[min+]);

             if i<> then

             begin

                 i:=pre[i];

                 aug:=his[i];

             end;

         end;

     writeln(sum-flow);

 end;

 begin

     init;

     sap;

 end.

巴特西

1565: [NOI2009]植物大战僵尸 - BZOJ

最新文章

热门文章