# P2805 [noi2009] plants vs Zombies (maximum weight closed subgraph & minimum cut)

2021-08-10 08:43:54

## P2805 [NOI2009] Plants vs. zombies ( Maximum weighted closed subgraph & Minimum cut )

Ideas ： Find plants that every plant can protect , That is, when selecting these plants , The plant must be selected , Satisfy the properties of closed subgraphs , And then build a map , The source point is connected with the positive weight point , Negative weight point and meeting point . In addition, we need to remove the ring of the graph , Because the plants on the ring can protect each other , You can sort the topology, and then take the mark to rebuild the map , Finally, run a maximum flow .

Time complexity ： O ( n 2 m ) O(n^2m) O(n2m)

``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=605,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,m,st,ed,h[N],cnt=1,dep[N],cur[N];
struct edge{
int to,nt,w;
}e[N*N];
e[++cnt]={v,h[u],w},h[u]=cnt,e[++cnt]={u,h[v],0},h[v]=cnt;
}
//dinic The board
bool bfs(){
queue<int>q;mst(dep,0);q.push(st),dep[st]=1;
while(!q.empty()){
int u=q.front();q.pop();cur[u]=h[u];
for(int i=h[u];i;i=e[i].nt){
int v=e[i].to,w=e[i].w;
if(w&&!dep[v]) dep[v]=dep[u]+1,q.push(v);
}
}return dep[ed];
}
int dfs(int u,int c){
if(u==ed) return c;
int res=c;
for(int &i=cur[u];i;i=e[i].nt){
int v=e[i].to,w=e[i].w;
if(w&&dep[v]==dep[u]+1){
int now=dfs(v,min(res,w));
if(!now) dep[v]=0;
e[i].w-=now,e[i^1].w+=now,res-=now;
}
if(!res) return c;
}return c-res;
}
vector<int>g[N];
int val[N*N],deg[N*N],vis[N];
int main(){
scanf("%d%d",&n,&m);
st=n*m,ed=st+1;
for(int i=0;i<st;i++){
scanf("%d",&val[i]);int q;scanf("%d",&q);
while(q--){
int x,y;scanf("%d%d",&x,&y);
g[i].pb(x*m+y);
deg[x*m+y]++;
}
}
for(int i=0;i<n;i++)
for(int j=1;j<m;j++)
g[i*m+j].pb(i*m+j-1),deg[i*m+j-1]++;
queue<int>q;
for(int i=0;i<st;i++) if(!deg[i]) q.push(i),vis[i]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int v:g[u]){
if(!vis[v]&&!(--deg[v])) q.push(v),vis[v]=1;
}
} 	// De ring
int ans=0;
for(int i=0;i<st;i++){		// Drawing
if(!vis[i]) continue;
for(int j:g[i]){
if(!vis[j]) continue;
}
}
while(bfs()) ans-=dfs(st,inf);printf("%d\n",max(ans,0)); // Run maximum flow
return 0;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
```

https://chowdera.com/2021/08/20210810084311856Z.html