```cpp
#include <cstdio>
#include <stack>
#include <queue>
#include <cstring>
#define UP(i,s,e) for(auto i=s; i!=e; ++i)
#define sd std::
namespace flow{ // }{{{
using typ = int;
constexpr int V = 1000*1000, E = V*6;
int iv, is, it;
struct Edge{int to, nxt, lf;} es[E*2+2];
constexpr int EDGE_NIL = 0;
constexpr int INF = 0x3f3f3f3f;
int h[V]; typ ex[V];
int head[V], gap[V+1];
sd stack<int> hnods[V];
int maxh = 0, cnt = 2;
void init(int v, int s, int t){
iv=v, is=s, it=t;
memset(gap, 0, sizeof gap);
memset(head, 0, sizeof head);
memset(ex, 0, sizeof ex);
maxh = 0, cnt = 2;
}
void addflow(int s, int t, int c, bool directed=false){
es[cnt] = {t, head[s], c}, head[s] = cnt++;
es[cnt] = {s, head[t], directed?c:0}, head[t] = cnt++;
}
void push(int x){
for(int i=head[x]; i!=EDGE_NIL; i=es[i].nxt){
if(x!=is && ex[x] == 0) break;
int t = es[i].to, w = es[i].lf;
if(!w || h[t] > h[x]) continue;
if(x==is || h[t] == h[x]-1){
int df = x==is ? w : (int)sd min(ex[x], (typ)w);
ex[x]-=df;
es[i].lf-=df, es[i^1].lf+=df;
if(ex[t] == 0 && t != it && t != is){
hnods[h[t]].push(t);
maxh = sd max(maxh, h[t]);
}
ex[t] += df;
}
}
}
void relabel(int x){
h[x] = iv;
for(int i=head[x]; i!=EDGE_NIL; i=es[i].nxt){
if(es[i].lf) h[x] = sd min(h[x], h[es[i].to]);
}
if(++h[x] < iv){
hnods[h[x]].push(x);
maxh = sd max(maxh, h[x]);
++gap[h[x]];
}
}
int gethiest(){
while(hnods[maxh].empty() && maxh >= 0) maxh--;
if(maxh == -1) return -1;
int ret = hnods[maxh].top();
hnods[maxh].pop();
return ret;
}
void bfs_init(){
memset(h, 0x3f, sizeof h);
h[it] = 0;
sd queue<int> todo;
todo.push(it);
while(!todo.empty()){
int s = todo.front();
todo.pop();
for(int i=head[s]; i!=EDGE_NIL; i=es[i].nxt){
int t=es[i].to;
if(es[i^1].lf && h[t]>h[s]+1){
h[t] = h[s]+1;
todo.push(t);
}
}
}
}
void hlpp(){
bfs_init();
if(h[is] == INF) return;
h[is] = iv;
UP(i, 0, iv) if(h[i]!=INF) gap[h[i]]++;
push(is);
int x;
while((x=gethiest())!=-1){
push(x);
if(ex[x]){
if(!--gap[h[x]]){
UP(i, 0, iv){
if(i==is || i==it) continue;
if(h[i]>h[x] && h[i]<iv+1) h[i] = iv+1;
}
}
relabel(x);
}
}
}
} // {}}}
namespace m{ // }{{{
int in, im;
void work(){
scanf("%d%d", &in, &im);
flow::init(in*im, 0, in*im-1);
UP(i, 0, in) UP(j, 0, im-1){
int x;
scanf("%d", &x);
flow::addflow(i*im+j, i*im+j+1, x, true);
}
UP(i, 0, in-1) UP(j, 0, im){
int x;
scanf("%d", &x);
flow::addflow(i*im+j, (i+1)*im+j, x, true);
}
UP(i, 0, in-1) UP(j, 0, im-1){
int x;
scanf("%d", &x);
flow::addflow(i*im+j, (i+1)*im+j+1, x, true);
}
flow::hlpp();
printf("%d\n", flow::ex[in*im-1]);
}
} // {}}}
int main(){ m::work(); return 0; }
```
by x383494 @ 2023-06-08 15:13:29
注意到 `stack<int> hnods[V];` 其中 $V=10^6$。
stack 的模板定义为：
```c++
template<
class T,
class Container = std::deque<T>
> class stack;
```
deque：
> 另一方面，deque 典型地拥有较大的最小内存开销；只保有一个元素的 deque 必须分配它的整个内部数组（例如 64 位 libstdc++ 上是对象尺寸的 8 倍；64 位 libc++ 上是对象尺寸的 16 倍和 4096 字节中的较大者）。
>
> —— cppreference
$10^6$ 个 deque 至少占用 600MB 内存。
by reveal @ 2023-06-08 15:34:20
感谢，此帖终结，是我的问题orz
by x383494 @ 2023-06-08 20:17:17