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