「bzoj2132」圈地计划 - 最小割+捆绑模型+二分图 | Bill Yang's Blog

「bzoj2132」圈地计划 - 最小割+捆绑模型+二分图

题目大意

    最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解,这块土地是一块矩形的区域,可以纵横划分为$N\times M$块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境,每块小区域建造商业区和工业区能取得不同的经济价值。更具体点,对于第$i$行第$j$列的区域,建造商业区将得到$A_{ij}$收益,建造工业区将得到$B_{ij}$收益。另外不同的区域连在一起可以得到额外的收益,即如果区域$(i,j)$相邻(相邻是指两个格子有公共边)有$K$块(显然$K$不超过$4$)类型不同于$(i,j)$的区域,则这块区域能增加$k\times C_{ij}$收益。经过Tiger.S教授的勘察,收益矩阵$A,B,C$都已经知道了。你能帮GDOI求出一个收益最大的方案么?


题目分析

因为求最大收益,转化为总和-最小损失(割)。
考虑建立二元组模型。

得到不定方程组(仅考虑额外奖励):

可得:
$e=-C$。
中间的影响边容量为负!即彭天翼所说的$K\lt0$,考虑使用二分图二元组模型:

得到不定方程组(仅考虑额外奖励):

解得一组解:
$a=c=b=d=0,e=C$。

因为原图是网格图,因此满足二分图性质,可以采用以上模型,按照上述解建模即可。


代码

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=10005;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t); //反向层次图
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

const int Dirx[]= {0,1,-1,0,0},Diry[]= {0,0,0,1,-1};
int n,m,a[105][105],b[105][105],c[105][105],color[105][105],sum=0;

int id(int x,int y) {
return (x-1)*m+y;
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
a[i][j]=Get_Int(),sum+=a[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
b[i][j]=Get_Int(),sum+=b[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
c[i][j]=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
color[i][j]=((i+j)&1)?1:2;
int S=n*m+1,T=n*m+2;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
if(color[i][j]==1) {
dinic.AddEdge(S,id(i,j),a[i][j]);
dinic.AddEdge(id(i,j),T,b[i][j]);
} else {
dinic.AddEdge(S,id(i,j),b[i][j]);
dinic.AddEdge(id(i,j),T,a[i][j]);
}
for(int k=1; k<=4; k++) {
int nx=i+Dirx[k],ny=j+Diry[k];
if(nx<1||ny<1||nx>n||ny>m)continue;
dinic.AddEdge(id(i,j),id(nx,ny),c[i][j]);
dinic.AddEdge(id(nx,ny),id(i,j),c[i][j]);
sum+=c[i][j];
}
}
printf("%d\n",sum-dinic.maxflow(S,T));
return 0;
}
姥爷们赏瓶冰阔落吧~
0%