比赛 !信心赛 评测结果 AAAAAAAAEE
题目名称 海拔 最终得分 80
用户昵称 终焉折枝 运行时间 0.680 s
代码语言 C++ 内存使用 17.38 MiB
提交时间 2026-01-17 11:03:09
显示代码纯文本
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

#define int long long
const int MAXN = 300005;
const int MAXM = 2000005;
const int inf = 1e18;

int h[MAXN], tot = 1;
int cur[MAXN], d[MAXN];
int n, S, T;

struct node{
	int to, next, len;
}e[MAXM];

void add(int x, int y, int len){
	e[++ tot] = {y, h[x], len};
	h[x] = tot;
}

bool bfs(){
	memset(d, 0, sizeof(d));
	queue<int> q;
	q.push(S); d[S] = 1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int i = h[u];i;i = e[i].next){
			int v = e[i].to;
			if(!d[v] && e[i].len){
				d[v] = d[u] + 1;
				q.push(v);
				if(v == T) return true;
			}
		}
	}
	return false;
}

int dfs(int u, int mf){
	if(u == T) return mf;
	int cnt = 0;
	for(int i = cur[u];i;i = e[i].next){
		cur[u] = i; int v = e[i].to;
		if(d[v] == d[u] + 1 && e[i].len){
			int f = dfs(v, min(mf, e[i].len));
			e[i].len -= f; e[i ^ 1].len += f;
			cnt += f; mf -= f;
			if(mf == 0) break;
		}
	}
	if(cnt == 0) d[u] = 0;
	return cnt;
}

int dinic(){
	int flow = 0;
	while(bfs()){
		memcpy(cur, h, sizeof(h));
		flow += dfs(S, inf);
	}
	return flow;
}

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

signed main(){
	freopen("altitude.in", "r", stdin);
	freopen("altitude.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	S = hxf(0, 0); T = hxf(n, n);
	int val;
	for(int i = 0;i <= n;i ++){
		for(int j = 0;j < n;j ++){
			cin >> val;
			add(hxf(i, j), hxf(i, j + 1), val);
			add(hxf(i, j + 1), hxf(i, j), 0);
		}
	}
	for(int i = 0;i < n;i ++){
		for(int j = 0;j <= n;j ++){
			cin >> val;
			add(hxf(i, j), hxf(i + 1, j), val);
			add(hxf(i + 1, j), hxf(i, j), 0);
		}
	}
	for(int i = 0;i <= n;i ++){
		for(int j = 0;j < n;j ++){
			cin >> val;
			add(hxf(i, j + 1), hxf(i, j), val);
			add(hxf(i, j), hxf(i, j + 1), 0);
		}
	}
	for(int i = 0;i < n;i ++){
		for(int j = 0;j <= n;j ++){
			cin >> val;
			add(hxf(i + 1, j), hxf(i, j), val);
			add(hxf(i, j), hxf(i + 1, j), 0);
		}
	}

	cout << dinic() << '\n';

	return 0;
}