| 比赛 |
!信心赛 |
评测结果 |
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;
}