BZOJ1565[NOI2009]植物大戰僵尸——最大權閉合子圖+拓撲排序

題目描述

Plants vs. Zombies(PVZ)是最近十分風靡的一款小游戲。Plants(植物)和Zombies(僵尸)是游戲的主角,其中Plants防守,而Zombies進攻。該款游戲包含多種不同的挑戰系列,比如Protect Your Brain、Bowling等等。其中最為經典的,莫過于玩家通過控制Plants來防守Zombies的進攻,或者相反地由玩家通過控制Zombies對Plants發起進攻。

現在,我們將要考慮的問題是游戲中Zombies對Plants的進攻,請注意,本題中規則與實際游戲有所不同。游戲中有兩種角色,Plants和Zombies,每個Plant有一個攻擊位置集合,它可以對這些位置進行保護;而Zombie進攻植物的方式是走到植物所在的位置上并將其吃掉。

游戲的地圖可以抽象為一個N行M列的矩陣,行從上到下用0到N–1編號,列從左到右用0到M–1編號;在地圖的每個位置上都放有一個Plant,為簡單起見,我們把位于第r行第c列的植物記為Pr, c。

Plants分很多種,有攻擊類、防守類和經濟類等等。為了簡單的描述每個Plant,定義Score和Attack如下:

Score[Pr, c]

Zombie擊潰植物Pr, c可獲得的能源。若Score[Pr, c]為非負整數,則表示擊潰植物Pr, c可獲得能源Score[Pr, c],若為負數表示擊潰Pr, c需要付出能源 -Score[Pr, c]。

Attack[Pr, c]

植物Pr, c能夠對Zombie進行攻擊的位置集合。

Zombies必須從地圖的右側進入,且只能沿著水平方向進行移動。Zombies攻擊植物的唯一方式就是走到該植物所在的位置并將植物吃掉。因此Zombies的進攻總是從地圖的右側開始。也就是說,對于第r行的進攻,Zombies必須首先攻擊Pr, M-1;若需要對Pr, c(0≤c<M-1)攻擊,必須將Pr,M-1, Pr, M-2 … Pr, c+1先擊潰,并移動到位置(r, c)才可進行攻擊。

在本題的設定中,Plants的攻擊力是無窮大的,一旦Zombie進入某個Plant的攻擊位置,該Zombie會被瞬間消滅,而該Zombie沒有時間進行任何攻擊操作。因此,即便Zombie進入了一個Plant所在的位置,但該位置屬于其他植物的攻擊位置集合,則Zombie會被瞬間消滅而所在位置的植物則安然無恙(在我們的設定中,Plant的攻擊位置不包含自身所在位置,否則你就不可能擊潰它了)。

Zombies的目標是對Plants的陣地發起進攻并獲得最大的能源收入。每一次,你可以選擇一個可進攻的植物進行攻擊。本題的目標為,制定一套Zombies的進攻方案,選擇進攻哪些植物以及進攻的順序,從而獲得最大的能源收入。

輸入輸出格式

輸入格式:

輸入文件pvz.in的第一行包含兩個整數N, M,分別表示地圖的行數和列數。

接下來N×M行描述每個位置上植物的信息。第r×M + c + 1行按照如下格式給出植物Pr, c的信息:第一個整數為Score[Pr, c], 第二個整數為集合Attack[Pr, c]中的位置個數w,接下來w個位置信息(r’, c’),表示Pr, c可以攻擊位置第r’ 行第c’ 列。

輸出格式:

輸出文件pvz.out僅包含一個整數,表示可以獲得的最大能源收入。注意,你也可以選擇不進行任何攻擊,這樣能源收入為0。

說明

約20%的數據滿足1 ≤ N, M ≤ 5;

約40%的數據滿足1 ≤ N, M ≤ 10;

約100%的數據滿足1 ≤ N ≤ 20,1 ≤ M ≤ 30,-10000 ≤ Score ≤ 10000

?

能源收入有正有負,再看數據范圍20*30很容易想到是最大權閉合子圖。

關鍵就是建模,首先要從源點連向正能源的點,從負能源(邊權要轉正)的點連向匯點。第二步從被保護的點連向保護的點(至于原因下面會解釋)。最后因為僵尸只能從右往左走,所以對于一行左面的點相當于被右面的點保護,所以要從左面的點連向右面的點。因為有些點之間互相保護,所以這些點一定不能到達(就是有環),被這些點保護的點也就不能到達,所以我們要從網絡中把這些點去掉,判環最簡單的方法自然是拓撲排序了,把排序到的點標記上表示可以增廣。將圖中所有反向邊進行拓撲排序,如果之前連的是從保護點到被保護點的話,刪掉的就是環和保護環的點,而不是被環保護的點。

拓撲排序之后直接跑最大流(也就是最小割),把正能源和(正點權)減掉最小割就得出答案了,但要注意,正能源和不要把刪掉的點也計算進去(我之前就是因為這里一直WA)。

最后附上代碼。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
queue<int>Q;
int next[1000001];
int to[1000001];
int val[1000001];
int head[1000001];
int tot=1;
int q[1000001];
int vis[1000];
int n,m;
int S,T;
int ans;
int s[1000];
int x,y;
int sum;
int num;
int d[1000001];
int inv[10000];
const int INF=0x3f3f3f3f;
void add(int x,int y,int v)
{tot++;next[tot]=head[x];head[x]=tot;to[tot]=y;val[tot]=v;tot++;next[tot]=head[y];head[y]=tot;to[tot]=x;val[tot]=0;inv[x]++;
} 
bool bfs(int S,int T)
{int r=0;int l=0;memset(d,-1,sizeof(d));q[r++]=S;d[S]=0;while(l<r){int now=q[l];for(int i=head[now];i;i=next[i]){if(d[to[i]]==-1&&val[i]!=0&&vis[to[i]]==1){d[to[i]]=d[now]+1;q[r++]=to[i];}}l++;}if(d[T]==-1){return false;}else{return true;}
}
int dfs(int x,int flow)
{if(x==T){return flow;}int now_flow;int used=0;for(int i=head[x];i;i=next[i]){if(d[to[i]]==d[x]+1&&val[i]!=0&&vis[to[i]]==1){now_flow=dfs(to[i],min(flow-used,val[i]));val[i]-=now_flow;val[i^1]+=now_flow;used+=now_flow;if(now_flow==flow){return flow;}}}if(used==0){d[x]=-1;}return used;
}
void dinic()
{while(bfs(S,T)==true){ans+=dfs(S,INF);}
}
int main()
{scanf("%d%d",&n,&m);S=n*m+1;T=n*m+2;for(int i=1;i<=n*m;i++){scanf("%d",&s[i]);if(s[i]>0){add(S,i,s[i]);}else if(s[i]<0){add(i,T,-s[i]);}scanf("%d",&num);while(num--){scanf("%d%d",&x,&y);add(x*m+y+1,i,INF);}if(i%m){add(i,i+1,INF);}}for(int i=1;i<=n*m+2;i++){if(inv[i]==0){Q.push(i);}}while(!Q.empty()){int now=Q.front();vis[now]=1;if(s[now]>0){sum+=s[now];}Q.pop();for(int i=head[now];i;i=next[i]){if(i%2==1){inv[to[i]]--;if(inv[to[i]]==0){Q.push(to[i]);}}}}dinic();sum-=ans;printf("%d",sum);return 0;
}

轉載于:https://www.cnblogs.com/Khada-Jhin/p/9113200.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/277897.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/277897.shtml
英文地址,請注明出處:http://en.pswp.cn/news/277897.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

推送ActivityFeed到Teams

幾個月前&#xff0c;Teams 團隊又推出了新的 Graph API&#xff0c;讓 app 可以給用戶發送 Activity Feed。我們來看看如何做。 首先&#xff0c;我們的app需要使用較新的 manifest 1.7版本&#xff0c;當然如果使用最新的1.8版本就更好了。在manifest json中添加 webApplica…

RecycleView彈性滑動

還有點bug&#xff0c;建議使用 LinearSnapHelper rvPilotList.addOnScrollListener(new RecyclerView.OnScrollListener() {Overridepublic void onScrolled(NonNull RecyclerView recyclerView, int dx, int dy) {super.onScrolled(recyclerView, dx, dy);// …

關于深度學習,這些知識點你需要了解一下

深度學習概述 o 受限玻爾茲曼機和深度信念網絡 o Dropout o 處理不平衡的技巧 o SMOTE&#xff1a;合成少數過采樣技術 o 神經網絡中對成本敏感的學習 深度學習概述 在2006年之前&#xff0c;訓練深度監督前饋神經網絡總是失敗的&#xff0c;其主要原因都是導致…

發送不同類型的ActivityFeed

上一篇文章講到了如何使用最新的Graph API來給一個用戶發送一個簡單的 Activity Feed。我們這篇文章來詳細講一下發送三種不同類型的消息。 發送 Chat 相關的 Activity Notification API 為 POST https://graph.microsoft.com/beta/chats/{chat-id}/sendActivityNotification…

git add * 提示warning: LF will be replaced by CRLF in 解決辦法

在使用git的時候&#xff0c;每次執行 $ git add * 都會提示這樣一個警告消息&#xff1a; 雖然說沒有什么影響吧。 不過就是覺得太礙眼了&#xff0c; 按照這樣設置就沒有問題了: git config core.autocrlf false 這樣設置git的配置后在執行add操作就沒有問題了。 奮斗的年紀你…

git 放棄本地修改,強制拉取更新

開發時&#xff0c;對于本地的項目中修改不做保存操作&#xff08;或代碼改崩&#xff09;&#xff0c;可以用到Git pull的強制覆蓋&#xff0c;具體代碼如下&#xff1a; git fetch --all git reset --hard origin/master git pull //可以省略 git fetch 指令是下載遠程倉庫最…

發送ActivityFeed的隱藏功能

前兩篇文章介紹了如何發送 activity notification&#xff0c;這篇文章主要介紹兩個隱藏功能&#xff0c;實際上所謂的隱藏功能是指大家在閱讀官方文檔是會忽略的兩個點&#xff0c;但是實際上也是很實用的兩個功能點。 text 類型的 topic 之前文章中提到我們的 activity not…

Dispatch Queue 之 Invoke 當前隊列

&#xfffc; 轉載于:https://www.cnblogs.com/huahuahu/p/dispatch-queue-zhi-invoke-dang-qian-dui-lie.html

js或jQuery獲取當前屏幕的各種高度

Javascript: 網頁可見區域寬&#xff1a; document.body.clientWidth 網頁可見區域高&#xff1a; document.body.clientHeight 網頁可見區域寬&#xff1a; document.body.offsetWidth (包括邊線的寬) 網頁可見區域高&#xff1a; document.body.offsetHeight (包括邊線的高) …

Teams數據統計 - 用戶在線離線狀態

前幾天我在wechat的moments里看到以為朋友發了騰迅會議的對用戶個人的年度數據統計&#xff0c;看上去很有大數據感。 實際上 Teams 也具備的類似的能力&#xff0c;只是它把這個能力開放給了開發人員&#xff0c;我們可以通過強大的 Graph API&#xff0c;獲取大量的數據信息&…

我們是如何通過全球第一免費開源ERP Odoo做到項目100%交付

傳統友商ERP的交付過程 一、先初步需求調研&#xff0c;后選型功能模塊 傳統友商ERP第一件事情先對客戶方進行初步的調研&#xff0c;客戶方無論說什么&#xff0c;友商聽過算過&#xff0c;只關心你人數多少&#xff0c;有哪些人涉及到哪些模塊&#xff0c;接著對模塊進行所謂…

HDU 4747 Mex

4747 思路&#xff1a; 線段樹 先求出mex(1,1)&#xff0c; mex(1, 2) &#xff0c; mex(1,3)&#xff0c;...&#xff0c;mex(1&#xff0c;n)&#xff08;單調上升&#xff09;&#xff0c;先將這些mex放進線段樹里求和 然后再求出next[i]表示下一次出現a[i] 的位置 然后從前…

Teams數據統計 - 通話記錄

上篇文章介紹了如何獲取用戶的在線狀態&#xff0c;這篇文章我們記錄介紹如何統計用戶通話記錄。 首先&#xff0c;Teams為了安全&#xff0c;它要求 app 要有 CallRecords.Read.All 權限。然后就可以通過這個api來獲取 call record。 GET /communications/callRecords/{id}這…

linux下mysql的數據庫簡單備份腳本

應用于整個庫的備份。 #!/bin/bash PATH$PATH:/usr/local/mysql/bin:/usr/local/mysql/sbin # 數據庫名稱 databases(myname) # 備份目錄 basepath/home/databak/ cd $basepath if [ ! -d "$basepath" ]; thenmkdir -p "$basepath" fi#遍歷數據庫名稱 for …

解決JS浮點數(小數)計算加減乘除的BUG

2019獨角獸企業重金招聘Python工程師標準>>> //浮點數減法運算function FloatSub(arg1,arg2){var r1,r2,m,n;try{r1arg1.toString().split(".")[1].length}catch(e){r10}try{r2arg2.toString().split(".")[1].length}catch(e){r20}mMath.pow(10…

Teams數據統計 - 聊天消息

前兩篇文章介紹了如何對用戶的在線狀態和通話記錄進行數據統計。這篇文章我們來看看如何統計用戶的聊天消息。 在介紹具體 api 如何調用前&#xff0c;我們可以先看一下 Teams 里對于 Message 的層級結構&#xff0c;在 Teams 里&#xff0c;message有兩種&#xff0c;一種是 …

vis.js

1、官網&#xff1a;http://visjs.org/docs/network/ 2、示例&#xff1a; <!doctype html>  <html>     <head>     <title>vis.js</title>     <script type"text/javascript" src"vis.js"></scri…

暑期實習面試——艾锝科技,Python實習生

遠程筆試過&#xff0c;拒絕現場面轉載于:https://www.cnblogs.com/qinziang/p/9123339.html

Teams App 如何使用設備的能力

我們以前講到過&#xff0c;Teams有很多中可以擴展的方面&#xff0c;其中有一種是Tab&#xff0c;開發者可以開發一個web page/app&#xff0c;然后以tab的方式嵌入到teams里面。 除了基本的功能&#xff0c;這種tab也可以使用teams客戶端設備所帶的一些能力&#xff0c;比如…

實驗室3

實驗3.1 1 #include<stdio.h>2 int main()3 { long int sum,i;4 sum0;5 for(i22;i<1003;i20){6 sumsumi;7 }8 printf("sum%ld",sum);9 return 0; 10 } 11 1 #include<stdio.h>2 int main()3 { 4 long int…