样例过了全WA求助
查看原帖
样例过了全WA求助
369399
yizhiming楼主2022/4/25 14:55
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath> 
using namespace std;
int read(){
	char ch = getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){
		if(ch=='-'){
			f=-1;
		}
		ch = getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=x*10+ch-'0';
		ch = getchar();
	} 
	return x*f;
}
const int N = 400005;
const int M = N*10;
struct aaa{
	int nxt,to,num;
}edge[M];
int head[N],tot=1,S,T,inf = 0x3f3f3f3f;
void add(int u,int v,int x){
	edge[++tot].nxt = head[u];edge[tot].to = v;edge[tot].num = x;head[u] = tot;
	edge[++tot].nxt = head[v];edge[tot].to  =u;edge[tot].num = 0;head[v] = tot;
}
queue<int>q;
int dep[N];
bool bfs(){
	q.push(S);
	memset(dep,0,sizeof(dep));
	dep[S] = 1;
	while(!q.empty()){
		int p  =q.front();
		q.pop();
		for(int i=head[p];i;i=edge[i].nxt){
			int now = edge[i].to;
			if(!dep[now]&&edge[i].num){
				dep[now] = dep[p]+1;
				q.push(now);
			}
		}
	}
	return dep[T];
} 
int dfs(int u,int f){
	if(u==T){
		return f;
	}
	int used =0;
	for(int i=head[u];i&&f;i=edge[i].nxt){
		int now = edge[i].to;
		if(dep[now]==dep[u]+1&&edge[i].num){
			int w = dfs(now,min(edge[i].num,f));
			edge[i].num-=w;edge[i^1].num+=w;
			used+=w;f-=w;
		}	
	}
	if(!used){
		dep[u]  =0;
	}
	return used;
}
int ans;
void dinic(){
	while(bfs()){
		//cout<<"here"<<"\n";
		ans+=dfs(S,inf);
	}
}
int n,m,z,res;
int rk(int x,int y){
	return (x-1)*m+y;
}
int main(){
	//cin>>n>>m;
	n  =read();m  =read();
	S= 0;
	T = 6*n*m+1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			z = read();
			add(S,rk(i,j),z);
			res+=z;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			z = read();
			add(rk(i,j)+n*m,T,z);
			add(rk(i,j),rk(i,j)+n*m,inf);
			res+=z;
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			z= read();
			res+=z; 
			add(S,rk(i,j)+2*n*m,z);
			//add(rk(i,j),rk(i,j)+2*n*m,inf);
			//add(rk(i+1,j),rk(i,j)+2*n*m,inf);
			add(rk(i,j)+2*n*m,rk(i,j),inf);
			add(rk(i,j)+2*n*m,rk(i+1,j),inf);
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			z = read();
			res+=z;
			add(rk(i,j)+3*n*m,T,z);
			add(rk(i,j)+n*m,rk(i,j)+3*n*m,inf);
			add(rk(i+1,j)+n*m,rk(i,j)+3*n*m,inf);
			//add(rk(i,j)+3*n*m,rk(i,j)+n*m,inf);
			//add(rk(i,j)+3*n*m,rk(i+1,j)+n*m,inf);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			z = read();
			res+=z;
			add(S,rk(i,j)+4*n*m,z);
			//add(rk(i,j),rk(i,j)+4*n*m,inf);
			//add(rk(i,j+1),rk(i,j)+4*n*m,inf);
			add(rk(i,j)+4*n*m,rk(i,j),inf);
			add(rk(i,j)+4*n*m,rk(i,j+1),inf);
		} 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			z = read();
			res+=z;
			add(rk(i,j)+5*n*m,T,z);
			add(rk(i,j)+n*m,rk(i,j)+5*n*m,inf);
			add(rk(i,j)+n*m,rk(i,j+1)+5*n*m,inf);
			//add(rk(i,j)+5*n*m,rk(i,j)+n*m,inf);
			//add(rk(i,j)+5*n*m,rk(i,j+1)+n*m,inf);
		}
	}
	dinic();
	//cout<<res<<"  "<<ans<<"\n";
	cout<<res-ans<<'\n';
	return 0;
}
2022/4/25 14:55
加载中...