FZU 2143 Board Game(费用流)

题目大意

给定一个 $N \times M$ 的矩阵 $A$ 和数字 $k$。你有一个零矩阵 $B$,每次可以将矩阵 $B$ 中任意两个相邻元素(上下或左右)同时加 $1$,可以任意操作多次,但元素最大值不能超过 $k$。
求以下表达式的最小值: $$S = \sum_{i-1}^{N}\sum_{j-1}^{M}(A_{ij} - B_{ij})^{2} $$
$(1 \leq N, M, K \leq 9 )$ 时限 $1s$。


解题思路

最小费用流

观察公式可知,对于某个元素加 $1=>B_{ij}$,其 $S$ 增加了 $2 B_{ij} - 2 A_{ij} - 1 $。将 $B_{ij}$ 当成变量的话,显然该函数式是单调递增的。

由此我们以棋盘模型进行建图(在标准的棋盘上,通常把交替地着上黑色和白色) :

  • 源点 $s$ 向黑色方格连 $k$ 条容量为 $1$,费用为 $2 x - 2 A_{ij} - 1(1 \leq x \leq k)$ 的边
  • 黑色方格向相邻的白色方格连 $1$ 条容量为 $\infty$ ,费用为 $0$ 的边
  • 白色方格向汇点 $t$ 连 $k$ 条容量为 $1$,费用为 $2 x - 2 A_{ij} - 1(1 \leq x \leq k)$ 的边

然后跑最小费用流(非最大流),当到汇点 $t$ 的增广路的距离 $d[t] \geq 0$ 时,不再进行增广,停止算法执行(理由接下来会讲到)。答案就是 $sum + cost$。

建图的原理

我们先计算出原矩阵与零矩阵的 $S$ 值。接下来跑费用流时,每增加一个流,相当于进行了一次操作,那么与原图的差距就会缩小,而其费用就是每进行一次操作可以减小的 $S$ 值。由于对于每个点其边的费用是单调递增的,所以跑最小费用流可以保证其从小的流起(这也算是一种常见的网络流建模技巧了)。然后显然我们并不需要也不能跑最大流,而是当本次操作的费用变为非负时,意味着已经不能再减小 $S$ 了,也就不再需要增广了。

Ps: 一开始一直卡在费用流跑到什么时候结束,因为知道不是最大流… 已经遇到过不少次这种只跑最小费用不跑最大流的问题了,看来还是要多 review。


解题代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 10;
const int MAXM = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
int to, cap, cost, next;
Edge( int to = 0, int cap = 0, int cost = 0, int next = 0 ) : to(to), cap(cap), cost(cost), next(next) {}
} G[MAXM];
int n, m;
int tot, head[MAXN];
int d[MAXN], pre[MAXN];
int A[MAXN][MAXN];
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};

bool ok(int x, int y)
{

return 0 <= x && x < n && 0 <= y && y < m;
}
void init()
{

tot = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int cap, int cost = 0)
{

G[tot] = Edge(v, cap, cost, head[u]);
head[u] = tot++;
G[tot] = Edge(u, 0, -cost, head[v]);
head[v] = tot++;
}
bool spfa(int s, int t)
{

memset(pre, -1, sizeof(pre));
fill(d, d + n * m + 2, INF);
queue<int> que;
d[s] = 0;
que.push(s);
while( !que.empty() ) {
int u = que.front(); que.pop();
for( int i = head[u]; ~i; i = G[i].next ) {
Edge& e = G[i];
if( e.cap > 0 && d[e.to] > d[u] + e.cost ) {
d[e.to] = d[u] + e.cost;
pre[e.to] = i;
que.push(e.to);
}
}
}
return d[t] < 0;
}
int MinCostMaxFlow(int s, int t)
{

int cost = 0;
while( spfa(s, t) ) {
int Min = INF;
for( int i = pre[t]; ~i; i = pre[G[i ^ 1].to] ) {
Edge& e = G[i];
Min = min(Min, e.cap);
}
for( int i = pre[t]; ~i; i = pre[G[i ^ 1].to] ) {
Edge& e = G[i];
e.cap -= Min;
G[i ^ 1].cap += Min;
}
cost += d[t];
}
return cost;
}
int main()
{

int T, cas = 0;
scanf("%d", &T);
while( T-- ) {
init();
int k;
scanf("%d %d %d", &n, &m, &k);
int sum = 0;
for( int i = 0; i < n; ++ i ) {
for( int j = 0; j < m; ++ j ) {
scanf("%d", &A[i][j]);
sum += A[i][j] * A[i][j];
}
}
int s = 0, t = n * m + 1;
for( int i = 0; i < n; ++ i ) {
for( int j = 0; j < m; ++ j ) {
if( (i + j) & 1 ) {
for( int l = 1; l <= k; ++ l ) {
addEdge(i * m + j + 1, t, 1, 2 * l - 2 * A[i][j] - 1);
}
} else {
for( int l = 1; l <= k; ++ l ) {
addEdge(s, i * m + j + 1, 1, 2 * l - 2 * A[i][j] - 1);
}
for( int l = 0; l < 4; ++ l ) {
int x = i + dx[l];
int y = j + dy[l];
if( ok(x, y) ) {
addEdge(i * m + j + 1, x * m + y + 1, INF);
}
}
}
}
}
printf("Case %d: %d\n", ++cas, sum + MinCostMaxFlow(s, t));
}

return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!