BZOJ 1565 植物大战僵尸

时间:2021-08-04 06:55:07

http://www.lydsy.com/JudgeOnline/problem.php?id=1565

思路:由于植物之间有保护关系:(右边的植物保护左边的植物,植物攻击范围内的植物都被保护了),因此可以用最大权闭合子图。

 #include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define inf 0x7fffffff
struct edge{
int u,v;
}e[];
int tot,go[],first[],next[],flow[];
int op[],cnt[],dis[],n,m,mx[],all,ru[];
int id[][],w[][],S,T,nodes,pd[],c[];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y,int z){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
flow[tot]=z;
}
void add(int x,int y,int z){
insert(x,y,z);op[tot]=tot+;
insert(y,x,);op[tot]=tot-;
}
int dfs(int x,int f){
if (x==T) return f;
int sum=,mn=nodes;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (flow[i]&&dis[pur]+==dis[x]){
int save=dfs(pur,std::min(f-sum,flow[i]));
sum+=save;
flow[i]-=save;
flow[op[i]]+=save;
if (sum==f||dis[S]>=nodes) return sum;
}
if (flow[i]) mn=std::min(mn,dis[pur]);
}
if (sum==){
cnt[dis[x]]--;
if (cnt[dis[x]]==){
dis[S]=nodes;
}else{
dis[x]=mn+;
cnt[dis[x]]++;
}
}
return sum;
}
int main(){
n=read();m=read();
S=;nodes=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
id[i][j]=nodes++;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++){
w[i][j]=read();
int num=read();
for (int k=;k<=num;k++){
int x=read(),y=read();
x++;y++;
e[++all].u=id[i][j],e[all].v=id[x][y],ru[e[all].v]++;
}
}
for (int i=;i<=n;i++)
for (int j=m;j>;j--)
e[++all].u=id[i][j],e[all].v=id[i][j-],ru[id[i][j-]]++;
for (int i=;i<=all;i++)
insert(e[i].u,e[i].v,);
T=nodes;nodes++;
int top=;
for (int i=;i<=nodes-;i++)
if (ru[i]==)
pd[i]=,c[++top]=i;
while (top>){
int now=c[top--];
for (int i=first[now];i;i=next[i]){
int pur=go[i];
ru[pur]--;
if (ru[pur]==){
pd[pur]=;
c[++top]=pur;
}
}
}
tot=;
for (int i=;i<=nodes;i++)
first[i]=;
for (int i=;i<=all;i++)
if (pd[e[i].u]&&pd[e[i].v])
add(e[i].u,e[i].v,inf);
int sum=; all=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (pd[id[i][j]]){
if (w[i][j]>) add(id[i][j],T,w[i][j]),sum+=w[i][j];
else
if (w[i][j]<) add(S,id[i][j],-w[i][j]);
all++;
}
nodes=all;
int ans=;
while (dis[S]<nodes) ans+=dfs(S,inf);
printf("%d\n",sum-ans);
}

BZOJ 1565 植物大战僵尸的更多相关文章

  1. 洛谷 P2805 BZOJ 1565 植物大战僵尸

    题目描述 Plants vs. Zombies(PVZ)是最近十分风靡的一款小游戏.Plants(植物)和Zombies(僵尸)是游戏的主角,其中Plants防守,而Zombies进攻.该款游戏包含多 ...

  2. &lbrack;Android&rsqb; 转移&OpenCurlyDoubleQuote;植物大战僵尸2”存档的办法,无需root

    作者:zyl910 查过了很多文章,都说需要root后才能转移存档.但很多时候是不能root的,此时该怎么办呢? 我研究了很久,最终找到了一种办法,无需root也能转移存档. 一.备份 我用的是联想手 ...

  3. 32位汇编第六讲&comma;OllyDbg逆向植物大战僵尸&comma;快速定位阳光基址

    32位汇编第六讲,OllyDbg逆向植物大战僵尸,快速定位阳光基址 一丶基址,随机基址的理解 首先,全局变量的地址,我们都知道是固定的,是在PE文件中有保存的 但是高版本有了随机基址,那么要怎么解决这 ...

  4. 原生JS实现的h5小游戏-植物大战僵尸

    代码地址如下:http://www.demodashi.com/demo/12755.html 项目介绍 本项目是利用原生js实现的h5小游戏-植物大战僵尸,主要结合了一下自己对于h5小游戏的理解,结 ...

  5. 植物大战僵尸:寻找阳光掉落Call调用

    实验目标:通过遍历阳光产生的时间,寻找阳光产生的本地Call,使用代码注入器注入,自定义生成阳光 阳光CALL遍历技巧: 进入植物大战僵尸-> 当出现阳光后->马上搜索未知初始数值 返回游 ...

  6. java小项目之:植物大战僵尸,这个僵尸有点冷!内附素材源码

    Java小项目之:植物大战僵尸! <植物大战僵尸>是由PopCap Games开发的一款益智策略类单机游戏,于2009年5月5日发售,这款游戏可谓是无人不知无人不晓. 在我身边,上到40岁 ...

  7. 【BZOJ】【1565】【NOI2009】PVZ 植物大战僵尸

    网络流/最大权闭合子图+拓扑排序 感动死了>_<,一年多以前刚知道网络流的时候听说了这道名字很带感的题目,现在终于有实力切掉它了. 这题是最大权闭合子图模型的经典应用<_<,首 ...

  8. BZOJ 1565&colon; &lbrack;NOI2009&rsqb;植物大战僵尸

    1565: [NOI2009]植物大战僵尸 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 2317  Solved: 1071[Submit][Stat ...

  9. 【刷题】BZOJ 1565 &lbrack;NOI2009&rsqb;植物大战僵尸

    Description Plants vs. Zombies(PVZ)是最近十分风靡的一款小游戏.Plants(植物)和Zombies(僵尸)是游戏的主角,其中Plants防守,而Zombies进攻. ...

随机推荐

  1. &lbrack;css3&rsqb;叉叉旋转效果

    .close_frame{display:inline-block;height:14px;width:14px;background:url("../images/closeiframe. ...

  2. Mathmatics

     点 到直线 距离 公式 . 平面内

  3. Centos 内存占满 释放内存

    free -m 查看内存使用情况 top,然后按下shift+m,按内存占用百分比排序 centos 为了提高效率,把部分使用过的文件缓存到了内存里.如果不需要这样的文件性能,那就可以释放. 如下两个 ...

  4. react native 遇到的坑

    1.项目中新加入组件,应执行npm install命令 2.项目执行react-native run-android 报错,应进入android目录,执行gradlew.bat clean命令 3.L ...

  5. Hbase 学习笔记(一) Hbase的物理模型 Hbase为每个值维护了一个多级索引,即&lt&semi;key&comma; column family&comma; column name&comma; timestamp&gt&semi;

      比如第一个region 代表 0-100 第二个region 代表 101 -200的 分的越多越不好管理,但同时方便了并行化处理,并发度越高,处理的越快.mapreduce就是按照rowkey的 ...

  6. Java中异常的基本应用(一)

    在Java中,我们把异常当做一种对象来处理,正是异常机制的引入,使得我们的程序更加健壮.异常指示了一个不正常的条件,或者一个错误条件,简单地说就是一个中断了正常的指令流的事件.程序控制将无条件的抛至一 ...

  7. 牛客---java练习

    一. 1. abstract可以修饰方法和类,不能修饰属性.抽象方法没有方法体,即没有大括号{}.抽象类中的成员属性都是public static final类型的:成员方法都是public abst ...

  8. 虚幻4:2D游戏中实现二级或多级跳跃

    转自:http://www.52vr.com/article-729-1.html 闲来无事,想做个二级跳跃或者多级跳跃的方法.. 如下所示.即可实现.   第一步:角色蓝图中.设置跳跃事件 第二部: ...

  9. elasticsearch安装marvel插件

    Marvel插件要在Elasticsearch和Kibana中同时安装.Step 1: Install Marvel into Elasticsearch: bin/plugin install li ...

  10. 将 HttpPostedFile 转换成 Image 或者 Bitmap

    代码如下: HttpFileCollection httpfiles = context.Request.Files; files = httpfiles[i]; Image im = Image.F ...