求助(样例未过,输出279)(帮过样例回关)
查看原帖
求助(样例未过,输出279)(帮过样例回关)
1251345
2012_Zhang_楼主2025/2/4 21:35
#include<bits/stdc++.h>
using namespace std;
#define int long long
int inf=1e18;
const int maxn=5e5+5;
int tot=1,head[maxn],to[maxn],val[maxn],nxt[maxn],dep[maxn],now[maxn],d[6][2]={{1,0},{-1,0},{0,1},{0,-1},{0,0}};
int n,m,s,t,g,art[1005][1005],sci[1005][1005],art_ex[1005][1005],sci_ex[1005][1005];
int node(int a,int b){return (a-1)*m+b;}
int same_art(int a,int b){return n*m+(a-1)*m+b;}
int same_sci(int a,int b){return n*m*2+(a-1)*m+b;}
bool in_map(int a,int b){return a<=n&&a>=1&&b<=m&&b>=1;}
queue<int>q;
void add(int a,int b,int w){
	nxt[++tot]=head[a];
	to[tot]=b;
	val[tot]=w;
	head[a]=tot;
}
bool bfs(){
	for(int i=1;i<maxn;i++) dep[i]=inf;
	while(!q.empty()) q.pop();
	now[s]=head[s];
	dep[s]=0;
	q.push(s);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i];
			if(val[i]>0&&dep[y]==inf){
				dep[y]=dep[x]+1;
				now[y]=head[y];
				q.push(y);
				if(y==t) return 1;
			}
		}
	}
	return 0;
} 
int dfs(int x,int sum){
	if(x==t) return sum;
	int cnt,ans=0;
	for(int i=now[x];i&&sum>0;i=nxt[i]){
		now[x]=i;
		int y=to[i];
		if(val[i]>0&&dep[y]-dep[x]==1){
			cnt=dfs(y,min(sum,val[i]));
			if(cnt==0) dep[y]=inf;
			val[i]-=cnt;
			val[i^1]+=cnt;
			sum-=cnt;
			ans+=cnt;
		}
	}
	return ans;
}
signed main(){
	int ans=0;
	cin>>n>>m;
	int s=n*m*3+1,t=n*m*3+2;
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)cin>>art[i][j];
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)cin>>sci[i][j];
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)cin>>art_ex[i][j];
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)cin>>sci_ex[i][j];
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			add(s,node(i,j),art[i][j]);add(node(i,j),s,0);
			add(node(i,j),t,sci[i][j]);add(t,node(i,j),0);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			add(s,same_art(i,j),art_ex[i][j]);add(same_art(i,j),s,0);
			add(same_sci(i,j),t,sci_ex[i][j]);add(t,same_sci(i,j),0);
			for(int k=0;k<6;++k){
				int tx=i+d[k][0],ty=j+d[k][1];
				if(in_map(tx,ty)){
				    add(same_art(i,j),node(tx,ty),inf);add(node(tx,ty),same_art(i,j),0);
					add(node(tx,ty),same_sci(i,j),inf);add(same_sci(i,j),node(tx,ty),0);
				}
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cnt+=art[i][j]+sci[i][j]+art_ex[i][j]+sci_ex[i][j];
		}
	}
	while(bfs())ans+=dfs(s,inf);
	cout<<cnt-ans;
	return 0;
}
2025/2/4 21:35
加载中...