费用流练习的题目，跑了EK；

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=20010;
const int inf=1000000000;
int dis[N],lin[N],vis[N],incf[N],pre[N],s,t,ans,maxflow,tot=1,n,m,h[55][55];
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
struct gg {
    int y,next,flow,c;
}a[N];
inline void add(int x,int y,int flow,int c) {
    a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot; a[tot].flow=flow; a[tot].c=c;
    a[++tot].y=x; a[tot].next=lin[y]; lin[y]=tot; a[tot].flow=0; a[tot].c=-c;
}
inline bool spfa() {
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=t;i++) dis[i]=-inf;
    queue<int> q; 
    q.push(s); vis[s]=1; dis[s]=0;
    incf[s]=1<<30;
    while(q.size()) {
        int x=q.front(); q.pop(); vis[x]=0;
        for(int i=lin[x];i;i=a[i].next) {
            int y=a[i].y;
            if(!a[i].flow) continue;
            if(dis[y]<dis[x]+a[i].c) {
                dis[y]=dis[x]+a[i].c;
                incf[y]=min(incf[x],a[i].flow);//incf[x]； 
                pre[y]=i;
                if(!vis[y]) {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    if(dis[t]==-inf) return false;
    return true;
}
inline void update() {
    int x=t;
    while(x!=s) {
        int i=pre[x];
        a[i].flow-=incf[t];
        a[i^1].flow+=incf[t];
        x=a[i^1].y;
    }
    maxflow+=incf[t];
    ans+=dis[t]*incf[t];
}
inline int num(int x,int y) {
    return (x-1)*m+y;
}
int main() {
    read(n); read(m);
    tot=1;
    s=n*m<<1|1,t=s+1;
    add(s,1,2,0);//要求两条路径；
    add(2*n*m,t,2,0);//收流是也是两条；
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            read(h[i][j]);
            add(num(i,j),num(i,j)+n*m,1,h[i][j]);
            if(j+1<=m) add(num(i,j)+n*m,num(i,j+1),inf,0);
            if(i+1<=n) add(num(i,j)+n*m,num(i+1,j),inf,0);
        }
    add(1,n*m+1,inf,0);
    add(num(n,m),num(n,m)+n*m,inf,0);
    while(spfa()) update();
    cout<<ans<<endl;
    return 0;
}