正題

P2805

---

題目大意

在一個$n\times m$的平面上有若干植物，每個植物有其攻擊集合，吃掉一個植物要先吃掉該植物右邊的所有植物，且該植物不能在任何一個植物的攻擊集合內(nèi)，吃掉后有貢獻$a_{i,j}$，問你最大貢獻

---

解題思路

先按植物先后吃的順序連邊，然后跑拓撲序判斷哪些植物能吃

然后直接對能吃的植物跑最大權閉合子圖

---

code

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 610 using namespace std; int n,m,x,y,g,s,t,nm,ans,tot,tott,v[N],h[N],hd[N],dep[N],deg[N]; queue<int>d; struct rec {int to,nx,edge; }e[N*N<<1]; struct recc {int to,nx; }a[N*N]; const int inf=1e8; int get(int x,int y) {return x*m+y; } void add(int x,int y) {a[++tott].to=y;a[tott].nx=hd[x];hd[x]=tott;deg[y]++;return; } void addl(int x,int y,int z) {e[++tot].to=y;e[tot].edge=z;e[tot].nx=h[x];h[x]=tot;e[++tot].to=x;e[tot].edge=0;e[tot].nx=h[y];h[y]=tot;return; } void prebfs() {for(int i=0;i<=nm;++i)if(!deg[i]){d.push(i);if(v[i]>0){ans+=v[i];addl(s,i,v[i]);}else if(v[i]<0)addl(i,t,-v[i]);}while(!d.empty()){int x=d.front();d.pop();for(int i=hd[x];i;i=a[i].nx){int y=a[i].to;deg[y]--;if(!deg[y]){d.push(y);if(v[y]>0){ans+=v[y];addl(s,y,v[y]);}else if(v[y]<0)addl(y,t,-v[y]);}}}return; } bool bfs() {memset(dep,0,sizeof(dep));dep[s]=1;while(!d.empty())d.pop();d.push(s);while(!d.empty()){int x=d.front();d.pop();for(int i=h[x];i;i=e[i].nx){int y=e[i].to;if(dep[y]||!e[i].edge)continue;dep[y]=dep[x]+1;if(y==t)return true;d.push(y);}}return false; } int dfs(int x,int flow) {if(x==t)return flow;int rest=0,k;for(int i=h[x];i;i=e[i].nx){int y=e[i].to;if(dep[y]!=dep[x]+1||!e[i].edge)continue;k=dfs(y,min(e[i].edge,flow-rest));if(!k)dep[y]=0;rest+=k;e[i].edge-=k;e[i^1].edge+=k;if(flow==rest)return rest;}return rest; } int main() {scanf("%d%d",&n,&m);nm=get(n-1,m-1);s=nm+1;t=nm+2;tot=1;for(int i=0;i<n;++i)for(int j=0;j<m;++j){scanf("%d",&v[get(i,j)]);scanf("%d",&g);for(int k=1;k<=g;++k){scanf("%d%d",&x,&y);add(get(i,j),get(x,y));addl(get(x,y),get(i,j),inf);}if(j){add(get(i,j),get(i,j-1));addl(get(i,j-1),get(i,j),inf);}}prebfs();while(bfs())ans-=dfs(s,inf);printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的【网络流】植物大战僵尸（P2805）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。