忘了排版了。。代码大概是这样。。
```
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
# define M (4000+5)
# define N (200000+5)
# define inf 210000000
# define R register int
inline int read(){
char c=getchar();
int x=0,w=1;
while(c>'9'||c<'0')
{
if(c=='-')
w=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*w;
}
using namespace std;
struct E
{
int nex,to,dis;
} edge[N<<1];
int hea[N],num;
inline void add_edge(int from,int to,int dis)
{
edge[num].nex=hea[to];
edge[num].to=from;
edge[num].dis=0;
hea[to]=num++;
edge[num].nex=hea[from];
edge[num].to=to;
edge[num].dis=dis;
hea[from]=num++;
}
int n,m,d[N],p[M][M],s,t;
inline bool bfs()
{
memset(d,0,sizeof(d));
d[s]=1;
queue<int>q ;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(R i=hea[u]; ~i; i=edge[i].nex)
{
int v=edge[i].to;
if(!d[v]&&edge[i].dis>0)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
return d[t];
}
int Dfs(int u,int dis)
{
if(u==t||!dis) return dis;
int sum=0;
for(R i=hea[u]; ~i; i=edge[i].nex)
{
int v=edge[i].to;
if(d[v]==d[u]+1&&edge[i].dis>0)
{
int diss=Dfs(v,min(dis,edge[i].dis));
if(diss>0)
{
edge[i].dis-=diss;
edge[i^1].dis+=diss;
sum+=diss;
dis-=diss;
if(!dis) return sum;
}
}
}
return sum;
}
inline int dinic()
{
int Ans=0;
while (bfs())
Ans+=Dfs(s,inf);
return Ans;
}
int tot=0;
int main()
{
memset(hea,-1,sizeof(hea));
n=read(); m=read();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
p[i][j]=(i-1)*m+j;
t=n*m*6+1;
int e=n*m;
for(R i=1; i<=n; i++)
for(R j=1; j<=m; j++)
{
int w;
w=read();
add_edge(s,p[i][j],w);
tot+=w;
}
for(R i=1; i<=n; i++)
for(R j=1; j<=m; j++)
{
int l;
l=read();
add_edge(p[i][j],t,l);
tot+=l;
}
for(R i=1; i<n; i++)
for(R j=1; j<=m; j++)
{
int w;
w=read();
add_edge(s,p[i][j]+e,w);
add_edge(p[i][j]+e,p[i][j],inf);
add_edge(p[i][j]+e,p[i+1][j],inf);
tot+=w;
}
for(R i=1; i<n; i++)
for(R j=1; j<=m; j++)
{
int l;
l=read();
add_edge(p[i][j]+e*2,t,l);
add_edge(p[i][j],p[i][j]+e*2,inf);
add_edge(p[i+1][j],p[i][j]+e*2,inf);
tot+=l;
}
for(R i=1; i<=n; i++)
for(R j=1; j<m; j++)
{
int w;
w=read();
add_edge(s,p[i][j]+e*3,w);
add_edge(p[i][j]+e*3,p[i][j],inf);
add_edge(p[i][j]+e*3,p[i][j+1],inf);
tot+=w;
}
for(R i=1; i<=n; i++)
for(R j=1; j<m; j++)
{
int l;
l=read();
add_edge(p[i][j]+e*4,t,l);
add_edge(p[i][j],p[i][j]+e*4,inf);
add_edge(p[i][j+1],p[i][j]+e*4,inf);
tot+=l;
}
printf("%d\n",tot-dinic());
return 0;
}
```
by beretty @ 2018-02-08 16:30:22
吟游诗人就是强!!!
by Captain_Paul @ 2018-02-08 16:32:48
#吟游诗人强无敌
by Victorique @ 2018-05-22 19:21:40