1
2
3
4
5
6
7
8
9
10
#include<cstdio>
#define ll long long
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
int main(){
ll a=read(),b=read();
writeln(a+b);
}

这题求覆盖尽量少的路径使得阻断所有路,可转为最小割模型,也可以用spfa求从左边/下边到上边/右边的最短路,即选择这条路径阻断。

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
#include<memory.h>
#include<algorithm>
#include<cstdio>
#define ll int
#define inf 2000000001
#define maxn 100010
#define mod 100000000
#define For(i,x,y) for(ll i=x;i<=y;++i)
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll head[1000005],cur[1000005],vet[6000005],val[6000005],next[6000005];
ll n,m,tot=1,h[1000005],q[1000005],ans,S,T;
void add(ll x,ll y,ll w){
next[++tot]=head[x]; head[x]=tot; vet[tot]=y; val[tot]=w;
}
bool bfs(){
ll now,i;
memset(h,-1,sizeof(h));
ll t=0,w=1;
q[t]=S; h[1]=0;
while (t<w){
now=q[t]; t++;
for (i=head[now];i;i=next[i])
if (val[i] and h[vet[i]]<0){
q[w++]=vet[i];
h[vet[i]]=h[now]+1;
}
}
if (h[T]==-1) return 0;
return 1;
}
ll dfs(ll x,ll f){
if (x==T||!f) return f;
ll w,used=0;
for (ll i=cur[x];i;i=next[i])
if (val[i] and h[vet[i]]==h[x]+1){
w=dfs(vet[i],min(f-used,val[i]));
val[i]-=w; val[i^1]+=w; used+=w;
if (val[i]) cur[x]=i;
if (used==f) return f;
}
if (!used) h[x]=-1;
return used;
}
void dinic(){
while (bfs()){
For(i,1,T) cur[i]=head[i];
ans+=dfs(S,inf);
}
}
int main(){
n=read(); m=read();
S=1; T=n*m;
For(i,1,n) For(j,1,m-1){
ll x=read();
add(m*(i-1)+j,m*(i-1)+j+1,x);
add(m*(i-1)+j+1,m*(i-1)+j,x);
}
For(i,1,n-1) For(j,1,m){
ll x=read();
add(m*(i-1)+j,m*(i)+j,x);
add(m*(i)+j,m*(i-1)+j,x);
}
For(i,1,n-1) For(j,1,m-1){
ll x=read();
add(m*(i-1)+j,m*(i)+j+1,x);
add(m*(i)+j+1,m*(i-1)+j,x);
}
dinic();
writeln(ans);
}