萌新网络流95分求助
查看原帖
萌新网络流95分求助
169555
Kiloio楼主2021/7/23 17:58
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int inf=0x3f3f3f3f; 
int n,m,a[105][105],b[105][105],c[105][105],ans,last[8000005],tot=1,s,t,dis[8000005],cur[8000005],cnt[8000005],sum;
queue <int>	q;
struct node{
	int y,z,nex;
}e[8000005];
inline void add(int x,int y,int z){
	tot++;
	e[tot].y=y,e[tot].z=z,e[tot].nex=last[x],last[x]=tot;
	tot++;
	e[tot].y=x,e[tot].z=0,e[tot].nex=last[y],last[y]=tot;
}
inline void bfs(){
	q.push(t);
	dis[t]=1,cnt[1]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=last[u]; i; i=e[i].nex){
			int v=e[i].y;
			if(!dis[v]){
				dis[v]=dis[u]+1,cnt[dis[v]]++;
				q.push(v);
			}
		}
	}
}
inline int dfs(int u,int flow){
	int v,temp,delta=0;
	if(u==t){
		ans+=flow;
		return flow;
	}
	for(register int i=cur[u]; i; i=e[i].nex){
		v=e[i].y,cur[u]=i;
		if(e[i].z>0 && dis[u]==dis[v]+1){
			temp=dfs(v,min(e[i].z,flow-delta));
			e[i].z-=temp,e[i^1].z+=temp,delta+=temp;
			if(flow==delta){
				return delta;
			}
		}
	}
	cnt[dis[u]]--;
	if(cnt[dis[u]]==0){
		dis[s]=t+1;
	}
	dis[u]++,cnt[dis[u]]++,cur[u]=last[u];
	return delta;
}
inline int count(int i,int j){
	return (i-1)*m+j;
}
int main(){
	cin>>n>>m;
	s=0,t=n*m+1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d",&a[i][j]);
			sum+=a[i][j];
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d",&b[i][j]);
			sum+=b[i][j];
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d",&c[i][j]);
		}
	}
	int op;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			op=count(i,j);
			if((i+j)&1){
				add(s,op,a[i][j]),add(op,t,b[i][j]);
			}
			else{
				add(s,op,b[i][j]),add(op,t,a[i][j]);
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){			
			if((i+j)&1){
				op=count(i,j);
				if(i-1>=1) add(op,count(i-1,j),c[i][j]+c[i-1][j]),add(count(i-1,j),op,c[i][j]+c[i-1][j]),sum+=c[i][j]+c[i-1][j];
				if(i+1<=n) add(op,count(i+1,j),c[i][j]+c[i+1][j]),add(count(i+1,j),op,c[i][j]+c[i+1][j]),sum+=c[i][j]+c[i+1][j];
				if(j-1>=1) add(op,count(i,j-1),c[i][j]+c[i][j-1]),add(count(i,j-1),op,c[i][j]+c[i][j-1]),sum+=c[i][j]+c[i][j-1];
				if(j+1<=m) add(op,count(i,j+1),c[i][j]+c[i][j+1]),add(count(i,j+1),op,c[i][j]+c[i][j+1]),sum+=c[i][j]+c[i][j+1];
			}
		}
	}
	for(int i=s; i<=t; i++){
		cur[i]=last[i];
	}
	bfs();
	while(dis[s]<=t){
		dfs(s,inf);
	}
	//cout<<sum<<" ";
	cout<<sum-ans;
	return 0;
}
2021/7/23 17:58
加载中...