1565: NOI2009植物大战僵尸

Description

1565: NOI2009植物大战僵尸


Input

1565: NOI2009植物大战僵尸


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,-10 ≤ Score ≤ 10 。

 

 

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

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

1565: NOI2009植物大战僵尸
1565: NOI2009植物大战僵尸
  1 const
  2     maxn=22;
  3     maxm=33;
  4     inf=10;
  5 var
  6     d,a,first,q:array[0..maxn*maxm]of longint;
  7     next,last:array[0..maxn*maxm*maxn*maxm]of longint;
  8     map:array[0..maxn*maxm,0..maxn*maxm]of longint;
  9     n,m,tot,sum,cnt:longint;
 10  
 11 function calc(i,j:longint):longint;
 12 begin
 13     exit(i*m+j+1);
 14 end;
 15  
 16 procedure insert(x,y:longint);
 17 begin
 18     inc(tot);
 19     last[tot]:=y;
 20     next[tot]:=first[x];
 21     first[x]:=tot;
 22     inc(d[y]);
 23 end;
 24  
 25 procedure init;
 26 var
 27     i,j,k,l,r,x,y:longint;
 28 begin
 29     read(n,m);
 30     for i:=0 to n-1 do
 31         for j:=0 to m-1 do
 32             begin
 33                 read(a[calc(i,j)]);
 34                 read(k);
 35                 if j>0 then insert(calc(i,j),calc(i,j-1));
 36                 for l:=1 to k do
 37                     begin
 38                         read(x,y);
 39                         insert(calc(i,j),calc(x,y));
 40                     end;
 41             end;
 42     l:=1;r:=0;
 43     for i:=0 to n -1do
 44         if d[calc(i,m-1)]=0 then
 45         begin
 46             inc(r);
 47             q[r]:=calc(i,m-1);
 48         end;
 49     while l<=r do
 50         begin
 51             if a[q[l]]>0 then inc(sum,a[q[l]]);
 52             if a[q[l]]>0 then inc(map[0,q[l]],a[q[l]]);
 53             if a[q[l]]<0 then inc(map[q[l],n*m+1],-a[q[l]]);
 54             i:=first[q[l]];
 55             while i<>0 do
 56                 begin
 57                     dec(d[last[i]]);inc(map[last[i],q[l]],inf);
 58                     if d[last[i]]=0 then
 59                     begin
 60                         inc(r);
 61                         q[r]:=last[i];
 62                     end;
 63                     i:=next[i];
 64                 end;
 65             inc(l);
 66         end;
 67     cnt:=r;
 68 end;
 69  
 70 var
 71     dis,vh,his,pre:array[0..maxn*maxm]of longint;
 72     flow:longint;
 73  
 74 procedure sap;
 75 var
 76     i,j,aug,min:longint;
 77     flag:boolean;
 78 begin
 79     vh[0]:=cnt+2;
 80     i:=0;aug:=inf;
 81     while dis[i]<n*m+2 do
 82         begin
 83             his[i]:=aug;
 84             flag:=false;
 85             for j:=0 to n*m+1 do
 86                 if (map[i,j]>0) and (dis[i]=dis[j]+1) then
 87                 begin
 88                     flag:=true;
 89                     if aug>map[i,j] then aug:=map[i,j];
 90                     pre[j]:=i;
 91                     i:=j;
 92                     if i=n*m+1 then
 93                     begin
 94                         inc(flow,aug);
 95                         while i<>0 do
 96                             begin
 97                                 inc(map[i,pre[i]],aug);
 98                                 dec(map[pre[i],i],aug);
 99                                 i:=pre[i];
100                             end;
101                         aug:=inf;
102                     end;
103                     break;
104                 end;
105             if flag then continue;
106             min:=n*m+1;
107             for j:=0 to n*m+1 do
108                 if (map[i,j]>0) and (dis[j]<min) then min:=dis[j];
109             dec(vh[dis[i]]);
110             if vh[dis[i]]=0 then break;
             dis[i]:=min+1;
112             inc(vh[min+1]);
113             if i<>0 then
114             begin
115                 i:=pre[i];
116                 aug:=his[i];
117             end;
118         end;
119     writeln(sum-flow);
120 end;
121  
122 begin
123     init;
124     sap;
125 end.
View Code

 

更多相关文章
  • NOI2009植物大戰僵屍
    这题应该分两步来做: 1.拓扑排序,去掉无敌点 2.求最大闭合子图 需要注意几点: 1.拓扑排序时,如果(i,j)可以攻击到(x,y),那么增加(x,y)的入度,而不是(i,j)的入度      因为入度代表着要攻击它需要事先攻击几个点 2.求最大闭合子图时,用所有的正权点-最大流 3.求最大闭合子
  • BZOJ 1565 植物大戰僵屍(最大權閉合圖)
    题目链接:http://61.187.179.132/JudgeOnline/proble
  • 


    		    Polymorphic無處不在@植物大戰僵屍2
    最近玩了一下植物大战僵尸2,发现里面有一种东西叫"超级炮弹",这种东西应用到豌豆上,豌豆会
  • 


    		    Silverlight C# 游戏开发:Flyer11僵尸五子棋
    本来我是想将这个五子棋写成一个系列,分别从界面制作,到后台的代码实现完成它,结果发现时间确实紧张,只好将它们简单的结合到一起,实际上这个游戏完成的比较早,很早以前就有了,结果时过境迁竟然给忘记,实在不应该,使用Silverlight来实现这样的游戏非常容易,只需要使用Blend这样的工具将界面画的漂 ...
  • 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2831 题目大意:植物大战僵尸.给定种植植物时间间隔t,以及每个僵尸的到达时间v,生命d.问是否能赢. 解题思路: 按照打完每只Zombie之后剩余时间v-d,从小到大排序. 理由如下: 设打完第i只Z
  • 收起相关游戏 cytus 机械迷城 小小炼狱 deemo 神庙逃离 现代战争4零点行动 植物大战僵尸2中文版 时空幻境 无尽之剑3 超级救火队 迷你冲撞 大战僵尸鸟 侍魂2 flappy bird 混沌与秩序 时空猎
  • 今天给大家推荐一款超赞的神器:genymotion.一:什么是genymotion      genymotion是一款完全超越BlueStacks的安卓模拟器,正如它中文官网的介绍:快到极致的Android模拟器.      英文官网:http://www.genymotion.com/    
  • 零基礎學習iOS開發01前言03前景和難易度分析
    本文目录 一.iOS开发的前景 二.iOS开发的难易度 这讲继续介绍iOS初学者比较感兴趣的问题:iOS开发的前景如何.iOS开发的难易度.要想分析iOS开发的前景,首先你要搞清楚是哪个牛X公司在维护着iOS系统.是谁在背后支撑着全球的iOS开发者,那就是大名鼎鼎的苹果公司. 回到顶部 一.iOS开
一周排行