题意

给你一张网格图，边有边权，割去一条边的代价就是边权，求让左上角和右下角不联通的最小代价。

题解

这显然是个最小割问题，直接建图跑网络流就可以了。

注意这是一个无向图，所以建边需要两边都有边权。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,en,linkk[N*N],dep[N*N],t=1;
struct Edge{int val,z,next;}e[N*N*6];
bool bfs(){
    memset(dep,-1,sizeof(dep));
    dep[1]=0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=linkk[x];i;i=e[i].next){
            int y=e[i].val;
            if(dep[y]>=0||e[i].z==0)continue;
            dep[y]=dep[x]+1;
            q.push(y);
        }
    }
    return dep[en]>=0;
}
int dfs(int x,int in){
    if(x==en)return in;
    if(!in)return 0;
    int out=0;
    for(int i=linkk[x];i;i=e[i].next){
        int y=e[i].val;
        if(dep[y]!=dep[x]+1||e[i].z==0)continue;
        int t=dfs(y,min(in,e[i].z));
        out+=t;
        in-=t;
        e[i].z-=t;
        e[i^1].z+=t;
    }
    if(!out)dep[x]=-1;
    return out;
}
void ling(int x,int y,int z){e[++t]=(Edge){y,z,linkk[x]},linkk[x]=t;}
void add(int x,int y,int z){ling(x,y,z),ling(y,x,z);}
int id(int x,int y){return (x-1)*m+y;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++){
            int x;
            scanf("%d",&x);
            add(id(i,j),id(i,j+1),x);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++){
            int x;
            scanf("%d",&x);
            add(id(i,j),id(i+1,j),x);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++){
            int x;
            scanf("%d",&x);
            add(id(i,j),id(i+1,j+1),x);
        }
    en=n*m;
    int ans=0;
    while(bfs()){
        ans+=dfs(1,1e9);
    }
    printf("%d",ans);
}

原图最小割 = 最大流 = 对偶图最短路

对偶图最短路做法：

#include <bits/stdc++.h>
using namespace std;
//----------Dijkstra Start----------
//存边
const int MAXN = 2000000 + 5;
const int MAXM = 6000000 + 5;
struct Edge
{
    int v, w;
};
vector<Edge> e[MAXN]; //e[u]：u 为起点的所有边
void addEdge(int u, int v, int w)
{
    e[u].push_back((Edge){v, w});
}
//优先队列
struct Point
{
    int p, w; //优先队列中储存 Point：到 p 的距离为 w
};
struct cmp
{
    bool operator()(Point &a, Point &b)
    {
        return a.w > b.w;
    }
};
priority_queue<Point, vector<Point>, cmp> q;
//Dijkstra
int dis[MAXN];  //dis[i]：s -> i 距离
bool vis[MAXN]; //vis[i]：i 是否确定
void dijkstra(int n, int s)
{
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push((Point){s, 0});
    for (int t = 1; t <= n && q.size() > 0; t++)
    {
        //找到未确定且最近的点 now
        Point head = q.top();
        q.pop();
        while (vis[head.p] && q.size() > 0)
        {
            head = q.top();
            q.pop();
        }
        if (vis[head.p])
            break;
        int now = head.p;
        //确定该点
        vis[now] = true;
        //用 now 优化相邻点
        for (int i = 0; i < e[now].size(); i++)
        {
            //now->v：w
            int v = e[now][i].v;
            int w = e[now][i].w;
            if (dis[now] + w < dis[v])
            {
                dis[v] = dis[now] + w;
                q.push((Point){v, dis[v]});
            }
        }
    }
}
//----------Dijkstra End----------
int n, m, tot, s, t;
//第x行第y列的左下(flag==1)/右上(flag==0)的格子id
int id(int x, int y, int flag)
{
    return ((x - 1) * 2 + flag) * (m - 1) + y;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //输入图
    cin >> n >> m;
    tot = (n - 1) * (m - 1) * 2 + 2;
    s = tot - 1;
    t = tot;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m - 1; j++)
        {
            int w, p, q; //这条边对应的上下块编号;
            cin >> w;
            p = id(i - 1, j, 1);
            q = id(i, j, 0);
            if (i == 1)
                p = t;
            if (i == n)
                q = s;
            addEdge(p, q, w);
            addEdge(q, p, w);
        }
    for (int i = 1; i <= n - 1; i++)
        for (int j = 1; j <= m; j++)
        {
            int w, p, q; //这条边对应的左右块编号;
            cin >> w;
            p = id(i, j - 1, 0);
            q = id(i, j, 1);
            if (j == 1)
                p = s;
            if (j == m)
                q = t;
            addEdge(p, q, w);
            addEdge(q, p, w);
        }
    for (int i = 1; i <= n - 1; i++)
        for (int j = 1; j <= m - 1; j++)
        {
            int w, p, q; //这条边对应的两个块;
            cin >> w;
            p = id(i, j, 0);
            q = id(i, j, 1);
            addEdge(p, q, w);
            addEdge(q, p, w);
        }
    dijkstra(tot, s);
    cout << dis[t] << endl;
    return 0;
}

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

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cur[1000005];
namespace wxh666{
    //#define getchar getchar_unlocked
    //#define putchar putchar_unlocked
    #define sqrt(a) __builtin_sqrt(a)
    #define f(a,b,c) for(int a=b;a<=c;a++)
    #define ff(a,b,c) for(int a=b;a>=c;a--)
    #define g(n) f(i,1,n)
    #define df(n,m) g(n) f(j,1,m)
    #define max max_by_wxh
    template<typename T>
    inline T max_by_wxh(T x,T y) {return ((x)>(y)?(x):y);}
    template<typename T,typename ...Args>
    inline T max_by_wxh(T x,Args ...xs) {return max_by_wxh(x,max_by_wxh(xs...));}
    #define min min_by_wxh
    template<typename T>
    inline T min_by_wxh(T x,T y) {return ((x)<(y)?(x):y);}
    template<typename T,typename ...Args>
    inline T min_by_wxh(T x,Args ...xs) {return min_by_wxh(x,min_by_wxh(xs...));}
    template<typename T>
    inline void read(T &ans)
    {
        char ch=getchar();int f=1;ans=0;
        for(;!isdigit(ch);ch=getchar()) ch=='-'?f=-1:f=1;
        for(;isdigit(ch);ch=getchar()) ans=(ans<<3)+(ans<<1)+(ch&15);
        ans*=f;
        return;
    }
    template<typename T,typename ...Args>
    inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
    inline int read()
    {
        char ch=getchar();int f=1,ans=0;
        for(;!isdigit(ch);ch=getchar()) ch=='-'?f=-1:f=1;
        for(;isdigit(ch);ch=getchar()) ans=(ans<<3)+(ans<<1)+(ch&15);
        return f*ans;
    }
    #define in read()
    template<typename T>
    inline void pu(T x)
    {
        ios::sync_with_stdio(false);
        cout<<x;
        ios::sync_with_stdio(true);
        return;
    }
    template<typename T>
    inline void pk(T x)
    {
        ios::sync_with_stdio(false);
        cout<<x<<" ";
        ios::sync_with_stdio(true);
        return;
    }
    inline void pk(char x)
    {
        ios::sync_with_stdio(false);
        cout<<x;
        if(x!='\n') cout<<' ';
        ios::sync_with_stdio(true);
        return;
    }
    template<typename T,typename ...Args>
    inline void pu(T x,Args ...xs){pu(x);pu(xs...);}
    template<typename T,typename ...Args>
    inline void ppu(T x,Args ...xs){pu(x,xs...,'\n');}
    template<typename T,typename ...Args>
    inline void pk(T x,Args ...xs){pk(x);pk(xs...);}
    template<typename T,typename ...Args>
    inline void ppk(T x,Args ...xs){pk(x,xs...,'\n');}
    #define cs(dt,n,m) \
    for(int i=1;i<=n;i++)\
    {\
        for(int j=1;j<=m;j++)\
            printf("%lld ",dt[i][j]);\
        cout<<endl;\
    }
};using namespace wxh666;
namespace lsq {
    typedef int lsqxx;
    struct lq {
        struct lqbz {
            lsqxx v,w,nxt;
        } e[6000005];
        lsqxx h[1000005],cnt=1;
        inline void add(lsqxx u,lsqxx v,lsqxx w=1) {
            e[++cnt].v=v;
            e[cnt].w=w;
            e[cnt].nxt=h[u];
            h[u]=cnt;
        }
    void erase() {cnt=1;memset(h,0,sizeof(h));return;}
    #define F(z,u) for(int j=cur[u],v=z.e[j].v,w=z.e[j].w;j;j=z.e[j].nxt,v=z.e[j].v,w=z.e[j].w)
    }q;
};
using namespace lsq;
int n,m,s,t;
int x;
inline int two_one(int x,int y) {return (x-1)*m+y;}
int d[1000005],gas[1000005];
void bfs()
{
    memset(d,-1,sizeof(d));
    queue<int>p;
    gas[0]=1;d[t]=0;
    p.push(t);
    while(!p.empty())
    {
        int u=p.front();p.pop();
        F(q,u)
        {
            if(d[v]!=-1) continue;
            d[v]=d[u]+1;
            ++gas[d[v]];
            p.push(v);
        }
    }
    return;
    g(n)
    {
        f(j,1,m)
            pk(d[two_one(i,j)]);
        cout<<endl;
    }
    cout<<endl;
    f(i,0,n*m) ppk(i,gas[i]);
    exit(0);
}
int dfs(int u=s,int ins=INT_MAX)
{
    if(u==t) return ins;
    int out=0;
    F(q,u)
    {
        cur[u]=j;
        if(d[u]<=d[v]||!w) continue;
        int nt=dfs(v,min(w,ins));
        ins-=nt;out+=nt;
        q.e[j].w-=nt;q.e[j^1].w+=nt;
        if(!ins) return out;
    }
    if(!(--gas[d[u]])) d[s]=n*m+1;
    ++gas[++d[u]];
    cur[u]=q.h[u];
    return out;
}
int ISAP()
{
    int ans=0;
    memcpy(cur,q.h,sizeof(cur));
    bfs();
    while(d[s]<t) ans+=dfs();
    return ans;
}
signed main()
{
    cin>>n>>m;s=1,t=n*m;
    df(n,m-1) 
        read(x),
        q.add(two_one(i,j),two_one(i,j+1),x),
        q.add(two_one(i,j+1),two_one(i,j),x);
    df(n-1,m)
        read(x),
        q.add(two_one(i,j),two_one(i+1,j),x),
        q.add(two_one(i+1,j),two_one(i,j),x);
    df(n-1,m-1)
        read(x),
        q.add(two_one(i,j),two_one(i+1,j+1),x),
        q.add(two_one(i+1,j+1),two_one(i,j),x);
    cout<<ISAP()<<endl;
    return 0;
}

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
using namespace std;
int hed[1000005],nex[6000005],lb[6000005],cap[6000005];
int dep[1000005];
int s,t,n,m,x,lo=-1,mx=2147483640;
inline void add(int x,int y,int num)
{
    lo++;   
    nex[lo]=hed[x];
    hed[x]=lo;
    lb[lo]=y;
    cap[lo]=num;
}
int dfs(int x,int num)
{
    if(x==t || num==0) return num; 
    int c=0;
    for(int i=hed[x];i!=-1;i=nex[i])
    if(dep[lb[i]]==dep[x]+1 && cap[i]!=0)
    {
        int f=dfs(lb[i],min(cap[i],num));
        c+=f;
        num-=f;
        cap[i]-=f;
        cap[i^1]+=f;
        if(num==0) break;
    }
    if(c==0) dep[x]=-1;
    return c;
}
inline bool bfs()
{
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    queue <int> q;
    q.push(s);
    while(!q.empty())
    {
       int x=q.front();
       q.pop();
       for(int i=hed[x];i!=-1;i=nex[i])
       if(cap[i]!=0 && dep[lb[i]]==0)
       {
        dep[lb[i]]=dep[x]+1;
        q.push(lb[i]);
       }
    }

    if(!dep[t]) return false;
    return true;
}
inline int dinic_()
{
    int c=0;
    while(bfs()) c+=dfs(s,mx);
    return c;
}
int main()
{
    memset(hed,-1,sizeof(hed));
    scanf("%d%d",&n,&m);
    s=1;t=n*m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++)
    {
        scanf("%d",&x);
        add((i-1)*m+j,(i-1)*m+j+1,x);
        add((i-1)*m+j+1,(i-1)*m+j,x);
    }
    for(int i=1;i<n;i++)    
    for(int j=1;j<=m;j++)   
    {
        scanf("%d",&x);
        add((i-1)*m+j,(i-1)*m+j+m,x);
        add((i-1)*m+j+m,(i-1)*m+j,x);
    }
    for(int i=1;i<n;i++)    
    for(int j=1;j<m;j++)    
    {
        scanf("%d",&x);
        add((i-1)*m+j,(i-1)*m+j+m+1,x);
        add((i-1)*m+j+m+1,(i-1)*m+j,x);
    }
    printf("%d",dinic_()); 
    return 0;
}

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
const int inf=2147483640;
int hed[2000005],nex[8000005],lb[8000005],cap[8000005];
ll dis[2000005];
bool pa[2000005];
int x,n,m,S,T,lo;
void add(int x,int y,int num)
{
    lo++;
    nex[lo]=hed[x];
    hed[x]=lo;
    lb[lo]=y;
    cap[lo]=num;
}
void SPFA()
{
    for(int i=1;i<=T;i++) dis[i]=1e17;
    queue<int>q;dis[S]=0;
    q.push(S);pa[S]=1;
    while(!q.empty())
	{
        x=q.front();
        for(int i=hed[x];i!=0;i=nex[i])
        if(dis[lb[i]]>dis[x]+cap[i])
		{
            dis[lb[i]]=dis[x]+cap[i];
            if(!pa[lb[i]]) {pa[lb[i]]=1;q.push(lb[i]);}
        }
        q.pop();pa[x]=0;
    }
    printf("%lld",dis[T]);
}
int main()
{
    scanf("%d%d",&n,&m);
    if(n==1 || m==1)
	{
        int ans=inf;
        for(int i=1;i<max(n,m);i++)
		{
            scanf("%d",&x);ans=min(ans,x);
        }
        if(ans==inf) ans=0;
        printf("%d",ans);exit(0);
    }
    S=(n-1)*(m-1)*2+1;T=S+1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++)
	{
        scanf("%d",&x);
        if(i==1)
		{
            add(j*2,T,x);add(T,j*2,x);
        }
        else if(i==n)
		{
            add((n-2)*(m-1)*2+j*2-1,S,x);
            add(S,(n-2)*(m-1)*2+j*2-1,x);
        }   
        else
		{
            add((i-2)*(m-1)*2+j*2-1,(i-1)*(m-1)*2+j*2,x);
            add((i-1)*(m-1)*2+j*2,(i-2)*(m-1)*2+j*2-1,x);
        }
    }
    for(int i=1;i<n;i++)
    for(int j=1;j<=m;j++)
	{
        scanf("%d",&x);
        if(j==1)
		{
            add((i-1)*(m-1)*2+1,S,x);add(S,(i-1)*(m-1)*2+1,x);
        }
        else if(j==m)
		{
            add((i-1)*(m-1)*2+j*2-2,T,x);
            add(T,(i-1)*(m-1)*2+j*2-2,x);
        }
        else
		{
            add((i-1)*(m-1)*2+j*2-2,(i-1)*(m-1)*2+j*2-1,x);
            add((i-1)*(m-1)*2+j*2-1,(i-1)*(m-1)*2+j*2-2,x);
        }
    }
    for(int i=1;i<n;i++)
    for(int j=1;j<m;j++)
	{
        scanf("%d",&x);
        add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2-1,x);
        add((i-1)*(m-1)*2+j*2-1,(i-1)*(m-1)*2+j*2,x);
    }
    SPFA();
    return 0;
}