题目大意
给定一个
n
∗
m
n*m
n∗m 的矩阵，每个点可以选择
0
0
0 或
1
1
1 ，给定数组
A
i
,
j
A_{i,j}
Ai,j 和数组
B
i
,
j
B_{i,j}
Bi,j ，表示点
(
i
,
j
)
(i,j)
(i,j) 选择
0
0
0 获得
A
i
,
j
A_{i,j}
Ai,j 的价值，否则获得
B
i
,
j
B_{i,j}
Bi,j 的价值。
再给定数组
C
i
,
j
C_{i,j}
Ci,j 表示与
(
i
,
j
)
(i,j)
(i,j) 相邻（即点
(
i
−
1
,
j
)
,
(
i
,
j
−
1
)
,
(
i
+
1
,
j
)
,
(
i
,
j
+
1
)
(i-1,j),(i,j-1),(i+1,j),(i,j+1)
(i−1,j),(i,j−1),(i+1,j),(i,j+1)） 且与
(
i
,
j
)
(i,j)
(i,j) 选择一样时的附加价值，若有
k
k
k 个点相邻，则增加贡献为
k
∗
C
i
,
j
k*C_{i,j}
k∗Ci,j ，求最大的价值。
Input & Output
输入：第一行
n
,
m
n,m
n,m ，接下来三个
n
∗
m
n*m
n∗m 的矩阵分别表示矩阵
A
,
B
,
C
A,B,C
A,B,C 。
输出：一个整数，即最大价值。
数据范围
n , m ≤ 100 , 0 ≤ A i , j , B i , j , C i , j ≤ 1000 n,m \le 100,0 \le A_{i,j},B_{i,j},C_{i,j} \le 1000 n,m≤100,0≤Ai,j,Bi,j,Ci,j≤1000 。
思路
我们可以将题目看作：给定
n
∗
m
n*m
n∗m 个点，每个点可以选择
0
0
0 或
1
1
1 ，二者必须选一个，其中点之间若选相同的就有附加价值，求最大价值。
考虑到每一个点能且只能选一个，根据最小割的定义（最小代价使得图被割为两部分），可以根据总价值
−
-
− 最小割（最大流）
=
=
= 最大价值进行求解。
问题在于建图。矩阵
A
A
A 和
B
B
B 建图并不难，源点连向各个点赋为
A
A
A 的值，表示若不选
A
A
A 的代价，汇点同理，难点在于点与点之间的连边。
这涉及到了一种网络流模型：二元关系网络流 。
讲地详细的大佬博客：网络流二元关系 。
我们只需要在有价值之间的点分别连两条双向边就可以了。
之后就成为网络流版题了。
AC代码
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF 21000000
using namespace std;
long long n,m,s,t,cnt,sum,dep[400200],to[400200],nxt[400200],flo[400200];
int head[400200],hed[400200];
long long A[220][220],B[220][220],C[220][220],dian[220][220],nod,f[400400];
void xx(int u,int v,long long w)
{
cnt++;
to[cnt]=v;
flo[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
cnt++;
}
void pd(int a1,int a2,int b1,int b2,long long va)
{
if(!dian[a1][a2]||!dian[b1][b2])
return;
xx(dian[a1][a2],dian[b1][b2],va);
xx(dian[b1][b2],dian[a1][a2],0);
}
bool bfs()
{
memset(dep,-1,sizeof(dep));
memcpy(hed,head,sizeof(head));
int he=0,ta=1;
dep[s]=1;
f[1]=s;
while(he<ta)
{
he++;
int x=f[he];
for(int i=head[x];i!=-1;i=nxt[i])
{
int y=to[i];
// printf("%d %d %d %d\n",he,x,y,i);
if(dep[y]==-1&&flo[i])
{
dep[y]=dep[x]+1;
ta++;
f[ta]=y;
}
}
}
return dep[t]!=-1;
}
long long dfs(int x,long long flow)
{
// printf("%d %lld\n",x,flow);
if(x==t) return flow;
long long now=flow;
for(int i=hed[x];i!=-1;i=nxt[i])
{
hed[x]=i;
int y=to[i];
if(dep[y]==dep[x]+1&&flo[i])
{
long long d=dfs(y,min(now,flo[i]));
flo[i]-=d,flo[i^1]+=d;
now-=d;
if(now==0)
break;
}
}
return flow-now;
}
long long dinic()
{
long long ans=0;
while(bfs())
ans+=dfs(s,INF);
return ans;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d %d",&n,&m);
s=0,t=n*m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
nod++,dian[i][j]=nod;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&A[i][j]),sum+=A[i][j],xx(s,dian[i][j],A[i][j]),xx(dian[i][j],s,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&B[i][j]),sum+=B[i][j],xx(dian[i][j],t,B[i][j]),xx(t,dian[i][j],0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%lld",&C[i][j]);
if(i-1>0)
sum=(sum+C[i][j]+C[i-1][j]);
if(j-1>0)
sum=(sum+C[i][j]+C[i][j-1]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
pd(i,j,i-1,j,C[i][j]+C[i-1][j]);
pd(i,j,i,j-1,C[i][j]+C[i][j-1]);
pd(i,j,i+1,j,C[i][j]+C[i+1][j]);
pd(i,j,i,j+1,C[i][j]+C[i][j+1]);
}
printf("%lld\n",sum-dinic());
