当前位置:网站首页>P2805 [noi2009] plants vs Zombies (maximum weight closed subgraph & minimum cut)

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

2021-08-10 08:43:54 wx6110fa547fd20

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];
void add(int u,int v,int w){
	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;
			add(j,i,inf);
		}
		if(val[i]>0) add(st,i,val[i]),ans+=val[i];
			if(val[i]<0) add(i,ed,-val[i]);
	}
	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.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810084311856Z.html

随机推荐