ZR 集训 Day28 – 线性规划与网络流进阶

ooliver 发布于 10 小时前 69 次阅读 OI

AI 摘要

网络流不只是管道与容量，更是一场关于“后悔”的艺术。反向边提供了时光倒流的退流机制，上下界则让流量在约束中起舞。从EK到Dinic，从可行流到费用流，今天带你拆解这些精妙设计，真正理解如何榨干网络的每一滴价值。

好文推荐：一些网络流经典建模 - 洛谷专栏

网络流总结

之前初学网络流时并没有在博客上记录，昨天的网络流题也都是用二分图相关算法写的，所以今天先总结一下网络流相关的算法。

前置基础芝士

网络是指一个有向图 $G = (V,E)$，有两个特殊节点：源点 $S$ 和汇点 $T$。每条有向边 $(x,y) \in E$ 都有一个权值 $c(x,y)$，称为边的容量。若 $(x,y) \notin E$，则 $c(x,y) = 0$。

用 $f(x,y)$ 表示边 $(x,y)$ 上的流量，$c(x,y) - f(x,y)$ 称为边的剩余容量。通常用 $f(x,y)/c(x,y)$ 的形式标记边上的流量与容量。

可行流应该满足：

  1. 容量限制： $f(x,y) \le c(x,y)$
  2. 流量守恒： $\sum_{(u,x) \in E} f(u,x) = \sum_{(x,v) \in E} f(x,v), \quad x \neq S, x \neq T$。$\sum_{(S,v) \in E} f(S,v)$ 称为整个网络的流量。

最大流：从源点流向汇点的最大流量。

增广路：一条从源点到汇点的所有边的剩余容量 $\ge 0$ 的路径。

残留网：由网络中所有结点和剩余容量大于 0 的边构成的子图，这里的边包括有向边和其反向边。
建图时每条有向边 $(x,y)$ 都构建一条反向边 $(y,x)$，初始容量 $c(y,x) = 0$。
构建反向边的目的是提供一个“退流管道”，一旦前面的增广路堵死可行流，可以通过“退流管道”退流，提供了“后悔机制”。

网络最大流

EK 算法

一直循环找增广路，如果找到增广路，先把答案加上当前增广路的流量，再将增广路上经过的边全部减去流量，并给反向边加上流量；如果找不到增广路，退出循环，得到答案。

时间复杂度：$O(nm^2)$。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;
int h[N],idx=1;
struct node{
    int v,c,nxt;
}e[N*20];
int n,m,s,t;
int mf[N],pre[N];

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

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

int ek(){
    int ans=0;
    while(bfs()){
        int v=t;
        while(v!=s){
            int ei=pre[v];
            e[ei].c-=mf[t];
            e[ei^1].c+=mf[t];
            v=e[ei^1].v;
        }
        ans+=mf[t];
    }
    return ans;
}

signed main(){
    cin>>n>>m>>s>>t;
    while(m--){
        int u,v,c;
        cin>>u>>v>>c;
        add(u,v,c);
        add(v,u,0);
    }
    cout<<ek();
    return 0;
}

Dinic 算法

这里再引入一个概念：

分层图：我们从源点 $S$ 开始 BFS，给每个节点赋予一个层数，表示它距离源点 $S$ 的最短距离。分层的目的是为了使 DFS 时严格按照层数递归，避免走环。

Dinic 算法思想如下：

  1. 在残余网络上，用 BFS 从源点 $s$ 到汇点 $t$ 构造分层图；
  2. 在当前分层图上，使用 DFS 进行多路增广，在回溯时实时更新剩余容量。

直至在残余网络中，无法从源点 $s$ 到达汇点 $t$。

在 DFS 中，我们有一个当前弧优化，即如果节点 $u$ 的第 $i$ 条邻接边已经达到了容量上限（或者这条边后面的路径已经无法再推送流量了），那么在这一轮 DFS 的后续过程中，节点 $u$ 就不需要再检查第 $i$ 条边及之前的边了。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;
int h[N],idx=1;
struct node{
    int v,c,nxt;
}e[N*20];
int n,m,s,t,d[N],cur[N];
void add(int u,int v,int c){
    e[++idx]={v,c,h[u]};
    h[u]=idx;
}

bool bfs(){
    memset(d,0,sizeof d);
    queue<int> q;
    q.push(s);
    d[s]=1,cur[s]=h[s];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(!d[v]&&e[i].c){
                d[v]=d[u]+1;
                cur[v]=h[v];
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int sum){
    if(u==t) return sum;
    int res=0;
    for(int i=cur[u];i&&res<sum;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].c){
            int t=dfs(v,min(e[i].c,sum-res));
            if(!t) d[v]=0;
            e[i].c-=t,e[i^1].c+=t,res+=t;
        }
    }
    return res;
}

int dinic(){
    int ans=0;
    while(bfs()) ans+=dfs(s,1e18);
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s>>t;
    while(m--){
        int u,v,c;
        cin>>u>>v>>c;
        add(u,v,c);
        add(v,u,0);
    }
    cout<<dinic();
    return 0;
}

无源汇上下界可行流

有源汇和无源汇的可行流的最大区别就是有源汇的源点不需要满足流量平衡，而无源汇的由于没有源汇点，所以每一个点都需要满足流量平衡（流量平衡的定义上面有提到）。

我们建两个网络，一个下界网络，一个增量网络。下界网络的流量限制就是原网络的流量下界、增量网络的流量限制就是原网络的流量上界减去流量下界。

例如，对于以下网络：

建出来的下界网络和增量网络就是：

由于这个下界网络是不平衡的，我们考虑在增量网络上跑一个最大流，使得下界网络加上增量网络上跑出来的最大流之后变得平衡了。那这个增量网络怎么修改呢？

我们举两个例子：

对于点 $2$，它在下界网络上的净流入为 $3$，净流出为 $1$，所以我们希望在增量网络上它的流出流量比流入流量多 $2$，这样加起来就是平衡的了。所以我们在增量网络上新建一个源点 $S$，连一条从 $S$ 到 $2$ 号点的边，流量为 $2$，这样我们在增量网络上跑最大流后，抛去我们刚刚加的边，$2$ 号点的流出流量就肯定比流入流量大 $2$，符合条件。

对于点 $4$，它在下界网络上的净流入为 $,3$，净流出为 $5$，所以我们希望在增量网络上它的流出流量比流入流量少 $2$，所以我们在增量网络上新建一个汇点 $T$，连一条从 $4$ 号点到 $T$ 的边，流量为 $2$，同理的跑完最大流后就符合条件了。

对于每个点，我们都进行这种操作，得到加边后的增量网络如下：

之后对这个增量网络跑最大流。

对于可行流的判定，如果我们加的这些边都跑满了，即最大流等于我们额外添加的从 $S$ 开始的边的容量和（等价于等于额外添加的从流向 $T$ 的边的容量和），说明原网络有可行流。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;
int h[N],idx=1,n,m,s,t,d[N],cur[N],in[N],out[N],low[N],eid[N];
struct node{int v,c,nxt;}e[N*25];

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

bool bfs(){
    memset(d,0,sizeof d);
    queue<int> q;q.push(s);d[s]=1,cur[s]=h[s];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(!d[v]&&e[i].c){
                d[v]=d[u]+1;cur[v]=h[v];q.push(v);
                if(v==t)return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int sum){
    if(u==t)return sum;
    int res=0;
    for(int i=cur[u];i&&res<sum;i=e[i].nxt){
        cur[u]=i;int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].c){
            int t_fl=dfs(v,min(e[i].c,sum-res));
            if(!t_fl)d[v]=0;
            e[i].c-=t_fl;e[i^1].c+=t_fl;res+=t_fl;
        }
    }
    return res;
}

int dinic(){
    int flow=0;
    while(bfs())flow+=dfs(s,1e18);
    return flow;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;s=0,t=n+1;
    for(int i=1;i<=m;i++){
        int u,v,l,r;cin>>u>>v>>l>>r;
        low[i]=l;
        add(u,v,r-l);eid[i]=idx;
        add(v,u,0);
        out[u]+=l;in[v]+=l;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(in[i]>out[i]){
            ans+=in[i]-out[i];
            add(s,i,in[i]-out[i]);add(i,s,0);
        }
        else if(in[i]<out[i]){
            add(i,t,out[i]-in[i]);add(t,i,0);
        }
    }
    if(dinic()==ans){
        cout<<"Yes\n";
        for(int i=1;i<=m;i++) cout<<low[i]+e[eid[i]^1].c<<"\n";
    }
    else cout<<"No\n";
    return 0;
}

有源汇上下界可行流

首先我们考虑将有源汇转化为无源汇，不难发现，如下图，当我们从 $T$ 向 $S$ 连一条范围在 $[0,+\infty )$ 的边，这样就能使得源汇点满足流量守恒。

之后，我们借用无源汇上下界可行流的做法，建出下界网络与增量网络（注意区分原图的 $S$，$T$ 与增量网络新建的源汇点 $S'$，$T'$）：

按照无源汇上下界可行流， $S'$，$T'$ 为源汇点跑完最大流后，我们先排除掉不可行的情况。

接下来就是最妙的一步，对于原网络的一个可行流的流量，就应该是下界网络源点所有连出去的边的流量和加上增量网络中源点连出去的边（不包括 $S$ 连向 $T'$）的流量。由于网络是可行流，所以我们加的那些附加边是都跑满的，也就是说 $S$ 连向 $T'$ 的那条边应该是跑满的，它的流量就应该等于下界网络源点所有连出去的边的流量和。所以原网络的可行流流量就可以看作是增量网络中源点连出去的边（包括 $S$ 连向 $T'$）的流量。由于流量守恒可知，它恰恰等于增量网络中 $T$ 流向 $S$ 的流量，因为只有这一条边连向 $S$。所以我们就找到了可行流。

有源汇上下界最大流

找到可行流后，我们紧接着很快就能找到最大流。

我们考虑在增量网络的残余网络上删除 $T$ 流向 $S$ 的这条边，之后以 $S$，$T$ 为源汇点再跑一遍最大流，得到的结果与先前算出来的可行流相加，就是原网络的最大流。

为什么是对的？

首先，原本的可行流保证了流量守恒，而对于我们添加的那些附加边，在可行的条件下是一定跑满了的，所以从 $S$，$T$ 是走不到 $S'$，$T'$ 的。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10,INF=1e18;
int idx=1,n,m,s,t;
int h[N],d[N],cur[N],in[N],out[N];
struct node{int v,c,nxt;} e[N*30];

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

bool bfs(){
    memset(d,0,sizeof d);
    queue<int> q;
    q.push(s);
    d[s]=1,cur[s]=h[s];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(!d[v]&&e[i].c){
                d[v]=d[u]+1,cur[v]=h[v];
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int sum){
    if(u==t) return sum;
    int res=0;
    for(int i=cur[u];i&&res<sum;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].c){
            int tfl=dfs(v,min(e[i].c,sum-res));
            if(!tfl)d[v]=0;
            e[i].c-=tfl;e[i^1].c+=tfl;res+=tfl;
        }
    }
    return res;
}

int dinic(){
    int fl=0;
    while(bfs()) fl+=dfs(s,INF);
    return fl;
}

signed main(){
    int S,T;
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++){
        int u,v,l,r;
        cin>>u>>v>>l>>r;
        add(u,v,r-l);
        add(v,u,0);
        out[u]+=l,in[v]+=l;
    }
    add(T,S,INF);
    int est=idx;
    add(S,T,0);
    int ss=0,tt=n+1,tot=0;
    for(int i=1;i<=n;i++){
        if(in[i]>out[i]){
            tot+=in[i]-out[i];
            add(ss,i,in[i]-out[i]);
            add(i,ss,0);
        }
        else if(in[i]<out[i]){
            add(i,tt,out[i]-in[i]);
            add(tt,i,0);
        }
    }
    s=ss,t=tt;
    if(dinic()!=tot){cout<<"N\n";return 0;}
    int flow=e[est^1].c;
    e[est].c=e[est^1].c=0;
    s=S,t=T;
    cout<<flow+dinic()<<"\n";
    return 0;
}

有源汇上下界最小流

如果说有源汇上下界最大流是在有源汇上下界可行流的基础上把残余网络榨干了，那有源汇上下界最小流就是把残余网络上能退的都退掉了。

实际上步骤差不多，先在增量网络的残余网络上删除 $T$ 流向 $S$ 的这条边，之后以 $T$ 为源点，$S$ 为汇点再跑一遍最大流。用可行流减去这次跑出来的答案就是原网络的最小流。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10,INF=1e18;
int idx=1,n,m,s,t;
int h[N],d[N],cur[N],in[N],out[N];
struct node{int v,c,nxt;} e[N*30];

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

bool bfs(){
    memset(d,0,sizeof d);
    queue<int> q;
    q.push(s);
    d[s]=1,cur[s]=h[s];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(!d[v]&&e[i].c){
                d[v]=d[u]+1,cur[v]=h[v];
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int sum){
    if(u==t) return sum;
    int res=0;
    for(int i=cur[u];i&&res<sum;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].c){
            int tfl=dfs(v,min(e[i].c,sum-res));
            if(!tfl)d[v]=0;
            e[i].c-=tfl;e[i^1].c+=tfl;res+=tfl;
        }
    }
    return res;
}

int dinic(){
    int fl=0;
    while(bfs()) fl+=dfs(s,INF);
    return fl;
}

signed main(){
    int S,T;
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++){
        int u,v,l,r;
        cin>>u>>v>>l>>r;
        add(u,v,r-l);
        add(v,u,0);
        out[u]+=l,in[v]+=l;
    }
    add(T,S,INF);
    int est=idx;
    add(S,T,0);
    int ss=0,tt=n+1,tot=0;
    for(int i=1;i<=n;i++){
        if(in[i]>out[i]){
            tot+=in[i]-out[i];
            add(ss,i,in[i]-out[i]);
            add(i,ss,0);
        }
        else if(in[i]<out[i]){
            add(i,tt,out[i]-in[i]);
            add(tt,i,0);
        }
    }
    s=ss,t=tt;
    if(dinic()!=tot){cout<<"N\n";return 0;}
    int flow=e[est^1].c;
    e[est].c=e[est^1].c=0;
    s=T,t=S;
    cout<<flow-dinic()<<"\n";
    return 0;
}

最小费用最大流

从最大流到费用流：

  • 最大流：边权无差异（可看作 $1$），每次通过 BFS 寻找边数最短路进行分层（$d[v] = d[u] + 1$），以保证多项式时间复杂度。
  • 费用流：要求流量最大且费用最小。根据 SSP 理论（连续最短路算法），每次必须沿着当前残量网络中费用最短的路径增广。

核心改动

  • 将 BFS 换成 SPFA，分层条件从 $d[v] = d[u] + 1$ 改为费用最短路条件：$d[v] = d[u] + w$。

一些需要注意的细节细节

  • 防死循环：若存在 $w = 0$ 的边，可能出现 $d[v] = d[u]$ 的同层环。DFS 中必须增加 `vis` 数组标记，防止死循环。
  • 负权反向边：退水反向边的费用为 $-w$，因此求最短路时需能处理负权边（用 SPFA）。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10,INF=0x3f3f3f3f3f3f3f3f;
int h[N],idx=1;
struct node{int v,c,w,nxt;}e[N*20];
int n,m,s,t,d[N],cur[N],vis[N];
int mf,mc;

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

bool spfa(){
    memset(d,0x3f,sizeof d);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    d[s]=0,vis[s]=1,cur[s]=h[s];
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v,c=e[i].c,w=e[i].w;
            if(c>0&&d[v]>d[u]+w){
                d[v]=d[u]+w;
                cur[v]=h[v];
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return d[t]<INF;
}

int dfs(int u,int lim){
    if(u==t) return lim;
    vis[u]=1;
    int res=0;
    for(int i=cur[u];i&&res<lim;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v,c=e[i].c,w=e[i].w;
        if(!vis[v]&&d[v]==d[u]+w&&c>0){
            int k=dfs(v,min(c,lim-res));
            if(!k) d[v]=INF;
            else{
                e[i].c-=k;e[i^1].c+=k;
                res+=k;mc+=k*w;
            }
        }
    }
    vis[u]=0;
    return res;
}

void dinic(){
    while(spfa()) mf+=dfs(s,1e18);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s>>t;
    while(m--){
        int u,v,c,w;
        cin>>u>>v>>c>>w;
        add(u,v,c,w);
    }
    dinic();
    cout<<mf<<" "<<mc<<'\n';
    return 0;
}

题单

P5192 Shoot the Bullet | 东方文花帖

算是有源汇上下界最大流模板了，考虑以下建边：

  1. $S \rightarrow i \ (i\in [1,n])$，流量上下界：$[0,D_i]$
  2. $i \rightarrow j \ (i\in [1,n],j \in [1,m])$，流量上下界：$[L,R]$
  3. $j \rightarrow T \ (j \in [1,m])$，流量上下界：$[G_j,+\infty)$

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10,INF=1e18;
int idx=1,n,m,s,t;
int h[N],d[N],cur[N],in[N],out[N];
struct node{int v,c,nxt;} e[N*30];

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

bool bfs(){
    memset(d,0,sizeof d);
    queue<int> q;
    q.push(s);
    d[s]=1,cur[s]=h[s];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(!d[v]&&e[i].c){
                d[v]=d[u]+1,cur[v]=h[v];
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int sum){
    if(u==t) return sum;
    int res=0;
    for(int i=cur[u];i&&res<sum;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].c){
            int tfl=dfs(v,min(e[i].c,sum-res));
            if(!tfl)d[v]=0;
            e[i].c-=tfl;e[i^1].c+=tfl;res+=tfl;
        }
    }
    return res;
}

int dinic(){
    int fl=0;
    while(bfs()) fl+=dfs(s,INF);
    return fl;
}

signed main(){
    int S,T;
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++){
        int u,v,l,r;
        cin>>u>>v>>l>>r;
        add(u,v,r-l);
        add(v,u,0);
        out[u]+=l,in[v]+=l;
    }
    add(T,S,INF);
    int est=idx;
    add(S,T,0);
    int ss=0,tt=n+1,tot=0;
    for(int i=1;i<=n;i++){
        if(in[i]>out[i]){
            tot+=in[i]-out[i];
            add(ss,i,in[i]-out[i]);
            add(i,ss,0);
        }
        else if(in[i]<out[i]){
            add(i,tt,out[i]-in[i]);
            add(tt,i,0);
        }
    }
    s=ss,t=tt;
    if(dinic()!=tot){cout<<"N\n";return 0;}
    int flow=e[est^1].c;
    e[est].c=e[est^1].c=0;
    s=S,t=T;
    cout<<flow+dinic()<<"\n";
    return 0;
}

P2774 方格取数问题

不难发现，如果你看了我最开始推荐的文章，这个问题属于文章里的文理分科问题，即相邻的两个格子不能被选在同一个集合内。

我们按下标和的奇偶性染色，相邻格子连一条边权为正无穷的边，$S$ 向所有白色格子连一条边权为该点权值的边，每一个黑色点向 $T$ 连一条边权为该点权值的边。此时 $S$，$T$ 就是选与不选的两个集合，对于原图求最小割即可得出想要使两个集合没有交集的最小代价。

又由于最小割等于最大流，答案就应该是权值和减去最大流。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e4+5,M=1e5+5,inf=1e18;
int n,m,s,t,idx=1,tot;
int h[N],d[N],cur[N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

struct edge{
    int v,c,nxt;
}e[M<<1];

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

bool bfs(){
    memset(d,0,sizeof(d));
    queue<int> q;
    q.push(s);
    d[s]=1,cur[s]=h[s];
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(!d[v]&&e[i].c){
                d[v]=d[u]+1;
                cur[v]=h[v];
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int sum){
    if(u==t) return sum;
    int res=0;
    for(int i=cur[u];i&&res<sum;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].c){
            int fl=dfs(v,min(e[i].c,sum-res));
            if(!fl) d[v]=0;
            e[i].c-=fl,e[i^1].c+=fl,res+=fl;
        }
    }
    return res;
}

int dinic(){
    int ans=0;
    while(bfs()) ans+=dfs(s,inf);
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>m>>n;
    s=0,t=m*n+1;
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){
        int w;
        cin>>w;
        tot+=w;
        int u=(i-1)*n+j;
        if((i+j)&1){
            add(s,u,w);
            add(u,s,0);
            for(int k=0;k<4;k++){
                int ni=i+dx[k],nj=j+dy[k];
                if(ni<1||ni>m||nj<1||nj>n) continue;
                int v=(ni-1)*n+nj;
                add(u,v,inf);
                add(v,u,0);
            }
        }
        else{
            add(u,t,w);
            add(t,u,0);
        }
    }
    cout<<tot-dinic()<<"\n";
    return 0;
}