题目链接：戳我
按理说以dinic\(O(M*N^2)\)的时间复杂度应该是过不去的（呃我也知道这个上界很松）。但是最小割确实可以水过去？？
但是本着写正解的精神，我还是学了学平面图和对偶图，跑最短路的话时间复杂度应该是正确的。（大家可以去上网搜一下，或者看蒟蒻的OI网络流 简单学习笔记）
所以就。。。建图呗。这种题最难的不就是建图嘛。
建议大家画一个图（图的范例比如说ljh dalao的这张qwq）
具体细节可以看代码。
注意n=1或者m=1的情况要特判。
然后因为点的上限(n-1)(m-1)*2+1,所以空间一定注意要开够qwqwq
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define S 0
#define T (n-1)*(m-1)*2+1
#define MAXN 4000010
using namespace std;
int n,m,t,cur;
int dis[MAXN],done[MAXN],head[MAXN];
struct Node
{
int u,d;
friend bool operator <(struct Node x,struct Node y)
{return x.d>y.d;}
};
struct Edge{int nxt,to,dis;}edge[MAXN<<1];
inline void add(int from,int to,int dis)
{
edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,head[from]=t;
edge[++t].nxt=head[to],edge[t].to=from,edge[t].dis=dis,head[to]=t;
}
inline void dij()
{
priority_queue<Node>q;
memset(dis,0x3f,sizeof(dis));
memset(done,0,sizeof(done));
q.push((Node){S,0});dis[S]=0;
while(!q.empty())
{
int u=q.top().u; q.pop();
if(done[u]) continue;
done[u]=1;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(dis[u]+edge[i].dis<dis[v])
dis[v]=dis[u]+edge[i].dis,q.push((Node){v,dis[v]});
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
if(n==1)
{
int minn=2147483647,cur;
for(int i=1;i<m;i++)
scanf("%d",&cur),minn=min(minn,cur);
printf("%d\n",minn);
return 0;
}
if(m==1)
{
int minn=2147483647,cur;
for(int i=1;i<n;i++)
scanf("%d",&cur),minn=min(minn,cur);
printf("%d\n",minn);
return 0;
}
for(int i=1;i<=2*(n-1)+1;i+=2)
for(int j=1;j<m;j++)
{
scanf("%d",&cur);
if(i==1) add(S,j,cur);
else if(i==2*(n-1)+1) add((i-2)*(m-1)+j,T,cur);
else add((i-2)*(m-1)+j,(i-1)*(m-1)+j,cur);
}
for(int i=1;i<2*(n-1)+1;i+=2)
for(int j=1;j<=m;j++)
{
scanf("%d",&cur);
if(j==1) add(i*(m-1)+1,T,cur);
else if(j==m) add(S,(i-1)*(m-1)+m-1,cur);
else add((i-1)*(m-1)+j-1,i*(m-1)+j,cur);
}
for(int i=1;i<2*(n-1)+1;i+=2)
for(int j=1;j<m;j++)
{
scanf("%d",&cur);
add((i-1)*(m-1)+j,i*(m-1)+j,cur);
}
dij();
printf("%d\n",dis[T]);
return 0;
}