#include<cstdio>
#include<iostream>
#include<cstring>
#define M 100009
#define inf 2139062143
using namespace std;
int n,m,a[][],b[][],c[][],tot,cnt=,T,ans,head[M],d[M],q[*M],next[*M],u[*M],v[*M];
int xx[]={,,,-},yy[]={,-,,};
bool bfs()
{
memset(d,,sizeof(int)*(T+));
int h=,t=;
q[]=;
d[]=;
for(;h<t;)
{
h++;
int p=q[h];
for(int i=head[p];i;i=next[i])
if(!d[u[i]]&&v[i])
{
d[u[i]]=d[p]+;
if(d[T])
return ;
t++;
q[t]=u[i];
}
}
return ;
}
int dinic(int s,int f)
{
if(s==T)
return f;
int rest=f;
for(int i=head[s];i&&rest;i=next[i])
if(v[i]&&d[u[i]]==d[s]+)
{
int now=dinic(u[i],min(rest,v[i]));
if(!now)
d[u[i]]=;
v[i]-=now;
v[i^]+=now;
rest-=now;
}
return f-rest;
}
void jia1(int a1,int a2,int a3)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
v[cnt]=a3;
return;
}
void jia(int a1,int a2,int a3)
{
jia1(a1,a2,a3);
jia1(a2,a1,);
return;
}
int main()
{
scanf("%d%d",&n,&m);
T=n*m+;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
tot+=a[i][j];
a[i][j]*=;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&b[i][j]);
tot+=b[i][j];
b[i][j]*=;
}
for(int i=;i<n;i++)
for(int j=;j<=m;j++)
{
int a1;
scanf("%d",&a1);
tot+=a1;
a[i][j]+=a1;
a[i+][j]+=a1;
jia((i-)*m+j,i*m+j,a1);
jia(i*m+j,(i-)*m+j,a1);
}
for(int i=;i<n;i++)
for(int j=;j<=m;j++)
{
int a1;
scanf("%d",&a1);
tot+=a1;
b[i][j]+=a1;
b[i+][j]+=a1;
jia((i-)*m+j,i*m+j,a1);
jia(i*m+j,(i-)*m+j,a1);
}
for(int i=;i<=n;i++)
for(int j=;j<m;j++)
{
int a1;
scanf("%d",&a1);
tot+=a1;
a[i][j]+=a1;
a[i][j+]+=a1;
jia((i-)*m+j,(i-)*m+j+,a1);
jia((i-)*m+j+,(i-)*m+j,a1);
}
for(int i=;i<=n;i++)
for(int j=;j<m;j++)
{
int a1;
scanf("%d",&a1);
tot+=a1;
b[i][j]+=a1;
b[i][j+]+=a1;
jia((i-)*m+j,(i-)*m+j+,a1);
jia((i-)*m+j+,(i-)*m+j,a1);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
jia(,(i-)*m+j,a[i][j]);
jia((i-)*m+j,T,b[i][j]);
}
for(;bfs();)
ans+=dinic(,inf);
printf("%d\n",tot-(ans/));
return ;
}
网络流最小割 建边非常神奇。
S向i连变容量为文[i]+文[i][j]/2,向j连边容量为文[j]+文[i][j]/2。i向T连边容量为理[i]+理[i][j]/2,j向T连边容量为理[j]+理[i][j]/2;i于j连边，容量为文[i][j]/2+理[i][j]/2.