1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
const int MAXM = 6000011;
const int MAXN = 1000011;
int inf;
int n,m;
int first[MAXN];
int ecnt;
int s,t;
int dis[MAXN];
int ans;
struct edge
{
int v,f;
int next;
}e[MAXM];
inline int getint()
{
int w=0,q=0;
char c=getchar();
while(c<'0'||c>'9'&&c!='-') c=getchar();
if(c=='-') q=1,c=getchar();
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
}
inline bool link(int x,int y,int z)
{
e[++ecnt].next=first[x];first[x]=ecnt;e[ecnt].v=y;e[ecnt].f=z;
e[++ecnt].next=first[y];first[y]=ecnt;e[ecnt].v=x;e[ecnt].f=z;
}
inline bool bfs()
{
memset(dis,127/3,sizeof dis);
int ceng=dis[t];
queue<int>q;
while(!q.empty()) q.pop();
dis[1]=1;q.push(1);//dis存层;
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=first[u];i;i=e[i].next)
{
if(e[i].f&&dis[e[i].v]==ceng)
{
dis[e[i].v]=dis[u]+1;
q.push(e[i].v);
}
}
if(dis[t]!=ceng) return 1;
}
return 0;
}
inline int maxflow(int now,int remain)
{
if(remain==0||now==t) return remain;
int flow=0;
for(int i=first[now];i;i=e[i].next)
{
if(dis[e[i].v]==dis[now]+1&&e[i].f)
{
int f=maxflow(e[i].v,min(remain,e[i].f));
if(f)
{
e[i].f-=f;e[i^1].f+=f;
flow+=f ; remain-=f;
if(remain==0) return flow;
}
else dis[e[i].v]=-1;
}
}
return flow;
}
inline void solve()
{
s=1,t=n*m;inf=1<<30;
while(bfs())
{
ans+=maxflow(s,inf);
}
printf("%d",ans);
}
int main()
{
n=getint(); m=getint();
int x; ecnt=1;
int nowx,nownex;
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++){
nowx=(i-1)*m+j,nownex=nowx+1;
x=getint(); link(nowx,nownex,x);
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++) {
nowx=(i-1)*m+j,nownex=nowx+m;
x=getint(); link(nowx,nownex,x);
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++) {
nowx=(i-1)*m+j,nownex=nowx+m+1;
x=getint(); link(nowx,nownex,x);
}
solve();
return 0;
}
|
近期评论