「BZOJ 2127」Happiness

Description

题目链接:BZOJ 2127

高一一班的座位表是个 $n\times m$ 的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。

作为计算机竞赛教练的 scp 大老板,想知道如何分配可以使得全班的喜悦值总和最大。

数据范围:$1\le n,m\le 100$,喜悦值均为小于等于 $5000$ 的非负整数。


Solution

考虑用网络流求解,总量减去最小割即为答案。

对于每个点 $(i,j)$,从 $s$ 连一条容量为选择文科的边,到 $t$ 连一条容量位选择理科的边。

对于 $(i,j)$ 和 $(i+1,j)$ 两个点的组合情况。假设这两个点同时选文科有 $w$ 的喜悦值,我们新建一个节点 $x$,从 $s$ 向 $x$ 连一条容量为喜悦值 $w$ 的边,再从 $x$ 向 $(i,j)$ 和 $(i+1,j)$ 分别连一条容量为 $\text{INF}$ 的边。对于左右前后、文科理科同理!

考虑这样做法的正确性:每个点自然只能选择一个科目(文科或理科),当某个点选择了文科 $s$,那么它向理科 $t$ 的边都应该要被断开。考虑哪些边会被断开:首先是它直接连向 $t$ 的边,其次是它和别的点组合连向 $t$ 的边,这样一来,这些边在网络图的中是有贡献的,意味着这些边的容量在答案中没有贡献,正确性证明完毕。

时间复杂度:$O((nm)^3)$($\text{Dinic}$)


Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define FOR(i,a,b) for(int i=a;i<=b;++i)

const int N=1e5+5,M=5e6+5;
const int inf=1<<30;
int n,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

int id(int x,int y) {
return (x-1)*m+y;
}
void add(int u,int v,int w) {
ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
memset(dep,0,sizeof(dep));
memcpy(cnr,lnk,sizeof(lnk));
std::queue<int> q;
q.push(s),dep[s]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=lnk[u];i;i=nxt[i]) {
int v=ter[i];
if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
}
}
return dep[t];
}
int dfs(int u,int t,int flow) {
if(u==t) return flow;
int ans=0;
for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
cnr[u]=i;
int v=ter[i];
if(val[i]&&dep[v]==dep[u]+1) {
int x=dfs(v,t,std::min(val[i],flow-ans));
if(x) val[i]-=x,val[i^1]+=x,ans+=x;
}
}
if(ans<flow) dep[u]=-1;
return ans;
}
int dinic(int s,int t) {
int ans=0;
while(bfs(s,t)) {
int x;
while((x=dfs(s,t,inf))) ans+=x;
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
int s=0,t=n*m+2*n*(m-1)+2*(n-1)*m+1,cnt=n*m;
int ans=0;
FOR(i,1,n) FOR(j,1,m) {
int x;
scanf("%d",&x),ans+=x;
addedge(s,id(i,j),x);
}
FOR(i,1,n) FOR(j,1,m) {
int x;
scanf("%d",&x),ans+=x;
addedge(id(i,j),t,x);
}
FOR(i,1,n-1) FOR(j,1,m) {
int x;
scanf("%d",&x),ans+=x;
addedge(s,++cnt,x);
addedge(cnt,id(i,j),inf);
addedge(cnt,id(i+1,j),inf);
}
FOR(i,1,n-1) FOR(j,1,m) {
int x;
scanf("%d",&x),ans+=x;
addedge(++cnt,t,x);
addedge(id(i,j),cnt,inf);
addedge(id(i+1,j),cnt,inf);
}
FOR(i,1,n) FOR(j,1,m-1) {
int x;
scanf("%d",&x),ans+=x;
addedge(s,++cnt,x);
addedge(cnt,id(i,j),inf);
addedge(cnt,id(i,j+1),inf);
}
FOR(i,1,n) FOR(j,1,m-1) {
int x;
scanf("%d",&x),ans+=x;
addedge(++cnt,t,x);
addedge(id(i,j),cnt,inf);
addedge(id(i,j+1),cnt,inf);
}
printf("%d\n",ans-dinic(s,t));
return 0;
}
0%