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