```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,st,ed;
int len,last[2*500010];
int vis[2*500010];
struct edge { int x,y,next,other,c; }a[2*500010];
queue<int> q;int dis[2*500010];
void ins(int x,int y,int c)
{
//printf("edge : %d %d\n",x,y);
int k1=++len,k2=++len;
a[k1].x=x,a[k1].y=y,a[k1].c=c;
a[k1].next=last[x],last[x]=k1;
a[k2].x=y,a[k2].y=x,a[k2].c=0;
a[k2].next=last[y],last[y]=k2;
a[k1].other=k2,a[k2].other=k1;
}
bool bt(int st,int ed)
{
memset(vis,false,sizeof(vis));
memset(dis,0,sizeof(dis));
dis[st]=1;q.push(st);
while (q.empty()==false)
{
int x=q.front();q.pop();
for (int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if (dis[y]==0 && a[k].c>0)
{
dis[y]=dis[x]+1;
q.push(y);
}
}
}
return dis[ed];
}
int dfs(int x,int ed,int f)
{
if (x==ed) return f;
vis[x]=true;
int s=0;
for (int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if (vis[y]==false && a[k].c>0 && s<f && dis[y]==dis[x]+1)
{
int t=dfs(y,ed,min(f-s,a[k].c));s+=t;
a[k].c-=t,a[a[k].other].c+=t;
}
}
vis[x]=false;
if (s==0) dis[x]=0;
return s;
}
int sum=0;
void dicnic(int st,int ed)
{
int x=0;
while (bt(st,ed)==true)
x+=dfs(st,ed,1<<30);
printf("%lld\n",sum-x);
}
signed main()
{
st=100*100*10+1,ed=st+1;
cin >> n >> m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
int x;cin >> x;sum+=x;
ins(st,(i-1)*m+j,x);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
int x;cin >> x;sum+=x;
ins((i-1)*m+j,ed,x);
}
for (int i=1;i<=n-1;i++)
for (int j=1;j<=m;j++)
{
int x;cin >> x;sum+=x;
ins(st,n*m*1+(i-1)*m+j,x);
ins(n*m*1+(i-1)*m+j,(i-1)*m+j,1<<30);
ins(n*m*1+(i-1)*m+j,(i)*m+j,1<<30);
}
for (int i=1;i<=n-1;i++)
for (int j=1;j<=m;j++)
{
int x;cin >> x;sum+=x;
ins(n*m*2+(i-1)*m+j,ed,x);
ins((i-1)*m+j,n*m*2+(i-1)*m+j,1<<30);
ins((i)*m+j,n*m*2+(i-1)*m+j,1<<30);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m-1;j++)
{
int x;cin >> x;sum+=x;
ins(st,n*m*3+(i-1)*m+j,x);
ins(n*m*3+(i-1)*m+j,(i-1)*m+j,1<<30);
ins(n*m*3+(i-1)*m+j,(i-1)*m+j+1,1<<30);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m-1;j++)
{
int x;cin >> x;sum+=x;
ins(n*m*4+(i-1)*m+j,ed,x);
ins((i-1)*m+j,n*m*4+(i-1)*m+j,1<<30);
ins((i-1)*m+j+1,n*m*4+(i-1)*m+j,1<<30);
}
dicnic(st,ed);
return 0;
}
```
by Loser_and_Joker @ 2021-05-19 21:13:11
怕是你写了个假的当前弧
by wmy_goes_to_thu @ 2021-05-19 21:16:41
@[expwmh](/user/107484) 事实上lz根本没写dinic
by Stinger @ 2021-05-19 21:28:11
。。。。。蒟蒻还没学。。。。
by Loser_and_Joker @ 2021-05-20 00:05:33
dicnic 又不是 dinic
by LJ07 @ 2023-08-04 16:30:45