比赛 !信心赛 评测结果 AAAAAAAATT
题目名称 海拔 最终得分 80
用户昵称 zhyn 运行时间 5.761 s
代码语言 C++ 内存使用 36.36 MiB
提交时间 2026-01-17 10:50:09
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 3000005 

int n; 
int s,t; 
const ll inf=1e18; 

struct node{
	ll v,w,ne;
}e[maxn];
int h[maxn],idx=1; 
ll mf[maxn],pre[maxn]; 


void add(int u,int v,ll w){
	e[++idx]={v,w,h[u]};
	h[u]=idx;
}

bool bfs(){
	memset(mf,0,sizeof(mf));
	queue<int>q;
	q.push(s);
	mf[s]=inf;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=e[i].ne){
			ll v=e[i].v;
			if(mf[v]==0&&e[i].w){
				mf[v]=min(mf[u],e[i].w);
				pre[v]=i;
				q.push(v);
				if(v==t){
					return true;
				}
			}
		}
	}
	return false;
}


ll ek(){
	ll flow=0;
	while(bfs()){
		int v=t;
		while(v!=s){
			int u=pre[v];
			e[u].w-=mf[t];
			e[u^1].w+=mf[t];
			v=e[u^1].v;
		}
		flow+=mf[t];
	}
	return flow;
}


inline int trans(int x,int y){
    return x*(n+1)+y;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	
	freopen("altitude.in","r",stdin);
	freopen("altitude.out","w",stdout);
	
	cin>>n;
	s=trans(0,0);
	t=trans(n,n);
	
	ll val;
	int x,y,u,v;
	for(x=0;x<=n;x++){
		for(y=0;y<n;y++){
			cin>>val;
			u=trans(x,y);
			v=trans(x,y+1);
			add(u,v,val);
			add(v,u,0);
		}
	}
	
	for(x=0;x<n;x++){
		for(y=0;y<=n;y++){
			cin>>val;
			u=trans(x,y);
			v=trans(x+1,y);
			add(u,v,val);
			add(v,u,0);
		}
	}
	for(x=0;x<=n;x++){
		for(y=0;y<n;y++){
			cin>>val;
			u=trans(x,y+1);
			v=trans(x,y);
			add(u,v,val);
			add(v,u,0);
		}
	}
	for(x=0;x<n;x++){
		for(y=0;y<=n;y++){
			cin>>val;
			u=trans(x+1,y);
			v=trans(x,y);
			add(u,v,val);
			add(v,u,0);
		}
	}
	
	cout<<ek()<<endl;
	return 0;
}