題目描述
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;
}