// 对偶图最短路 Dijkstra 算法 O(MlogN)
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int N=2e6,M=6e6;
int to[M],ne[M],ww[M],h[N],idx;
void add(int a,int b,int c){
  to[++idx]=b,ww[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m,s,t;
int d[N];
bool vis[N];

void dijkstra(){
  memset(d,0x3f,sizeof d); d[s]=0;
  priority_queue<pii,vector<pii>,greater<pii> > q;
  q.push({0,s});
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(vis[u])continue; vis[u]=1;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i],w=ww[i];
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        q.push({d[v],v});
      }
    }
  }
}
int get(int x,int y){
  return 2*x*(m-1)+2*y;
}
int main(){
  scanf("%d%d",&n,&m);
  s=0; t=2*(n-1)*(m-1)+1; //t对偶图终点编号
  int w,v1,v2;
  for(int i=1;i<=n;i++)for(int j=1;j<m;j++){ //横边
    scanf("%d",&w);
    v1=get(i-2,j)-1;
    v2=get(i-1,j);
    if(i==1) add(v2,t,w);
    else if(i==n) add(s,v1,w);
    else add(v1,v2,w),add(v2,v1,w);
  }
  for(int i=1;i<n;i++)for(int j=1;j<=m;j++){ //竖边
    scanf("%d",&w);
    v1=get(i-1,j)-1;
    v2=v1-1;
    if(j==1) add(s,v1,w);
    else if(j==m) add(v2,t,w);
    else add(v1,v2,w),add(v2,v1,w);
  }
  for(int i=1;i<n;i++)for(int j=1;j<m;j++){ //斜边
    scanf("%d",&w);
    v1=get(i-1,j)-1;
    v2=v1+1;
    add(v1,v2,w),add(v2,v1,w);
  }
  
  dijkstra();
  printf("%d",d[t]);
}

问题分析

本题可转化为求网格图中从左上角到右下角的最小割问题，利用最大流最小割定理，通过Dinic算法求解。将网格中的每个点视为图的顶点，相邻点之间的边容量为对应网格线的权重，通过构建流网络，计算从源点到汇点的最大流，即为最小割值。

代码实现

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

const int N = 1e6 + 10, M = 6e6 + 10, INF = 0x3f3f3f3f;
struct edge { int x, y, f, pre; } a[M];
int alen, last[N], cur[N];

void ins(int x, int y, int f) {
    alen++; a[alen] = edge{x, y, f, last[x]}; last[x] = alen;
    alen++; a[alen] = edge{y, x, f, last[y]}; last[y] = alen;
}

int n, m, st, ed, h[N];

bool bfs() {
    queue<int> Q; Q.push(st);
    memset(h, 0, sizeof(h)); h[st] = 1;
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (int k = last[x]; k; k = a[k].pre) if (a[k].f) {
            int y = a[k].y;
            if (!h[y]) {
                h[y] = h[x] + 1;
                Q.push(y);
            }
        }
    }
    return h[ed] > 0;
}

int dinic(int x, int f) {
    if (x == ed) return f;
    int sx = 0;
    for (int k = cur[x]; k; k = a[k].pre) if (a[k].f) {
        cur[x] = k;
        int y = a[k].y;
        if (h[y] == h[x] + 1) {
            int sy = dinic(y, min(a[k].f, f - sx));
            a[k].f -= sy; a[k ^ 1].f += sy;
            sx += sy; if (sx == f) return f;
        }
    }
    if (!sx) h[x] = 0;
    return sx;
}

int main() {
    scanf("%d%d", &n, &m);
    alen = 1; memset(last, 0, sizeof(last));
    // 水平边（同一行相邻点）
    for (int i = 0, x; i < n; i++)
        for (int j = 0; j < m - 1; j++) {
            scanf("%d", &x);
            ins(i * m + j + 1, i * m + j + 2, x);
        }
    // 垂直边（同一列相邻点）
    for (int i = 0, x; i < n - 1; i++)
        for (int j = 0; j < m; j++) {
            scanf("%d", &x);
            ins(i * m + j + 1, (i + 1) * m + j + 1, x);
        }
    // 斜向边（右下方对角线）
    for (int i = 0, x; i < n - 1; i++)
        for (int j = 0; j < m - 1; j++) {
            scanf("%d", &x);
            ins(i * m + j + 1, (i + 1) * m + j + 2, x);
        }
    st = 1; ed = n * m;
    int ans = 0;
    while (bfs()) {
        memcpy(cur, last, sizeof(last));
        ans += dinic(st, INF);
    }
    printf("%d\n", ans);
    return 0;
}

算法说明

1. 图的构建：将网格中的每个点（i,j）编号为i*m + j + 1，构建三类边：
   • 水平边：同一行相邻点，容量为水平网格线权重。
   • 垂直边：同一列相邻点，容量为垂直网格线权重。
   • 斜向边：右下方对角线相邻点，容量为斜向网格线权重。
2. Dinic算法：通过BFS构建层次图，确保增广路径的最短性；通过DFS寻找阻塞流，高效计算最大流，进而得到最小割值（即答案）。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10, M=6e6+10, INF=0x3f3f3f3f;
struct edge{int x, y, f, pre;} a[M]; int alen, last[N], cur[N]; 
void ins(int x, int y, int f)
{
    alen++; a[alen]=edge{x, y, f, last[x]}; last[x]=alen;
    alen++; a[alen]=edge{y, x, f, last[y]}; last[y]=alen;
}
int n, m, st, ed, h[N];
bool bfs()
{
    queue<int> Q; Q.push(st);
    memset(h, 0, sizeof(h)); h[st]=1;
    while(!Q.empty())
    {
        int x=Q.front(); Q.pop();
        for(int k=last[x]; k; k=a[k].pre) if(a[k].f)
        {
            int y=a[k].y;
            if(!h[y])
            {
                h[y]=h[x]+1;
                Q.push(y);
            }
        }
    }
    return (h[ed]>0);
} 
int dinic(int x, int f)
{
    if(x==ed) return f;
	int sx=0;
    for(int k=cur[x]; k; k=a[k].pre) if(a[k].f)
    {
    	cur[x]=k;
        int y=a[k].y;
        if(h[y]==(h[x]+1))
        {
            int sy=dinic(y, min(a[k].f, f-sx));
            a[k].f-=sy; a[k^1].f+=sy;
            sx+=sy; if(sx==f) return f;
        }
    }
    if(!sx) h[x]=0;
    return sx;
}
int main()
{
    scanf("%d%d",&n,&m);
    alen=1; memset(last, 0, sizeof(last));
    for(int i=0,x;i<n;i++)for(int j=0;j<m-1;j++)scanf("%d",&x),ins( i*m+j+1, i*m+j+2,x);
	for(int i=0,x;i<n-1;i++)for(int j=0;j<m;j++)scanf("%d",&x),ins( i*m+j+1, (i+1)*m+j+1,x);
	for(int i=0,x;i<n-1;i++)for(int j=0;j<m-1;j++)scanf("%d",&x),ins( i*m+j+1, (i+1)*m+j+2,x);
    st=1;ed=n*m;
	int ans=0;
    while(bfs())
	{
		memcpy(cur,last,sizeof(last));
		ans+=dinic(st, INF);
	}
    printf("%d\n", ans);
    return 0;
}