[解题报告][luoguP4311]士兵占领

BruceW 收录于 OI 解题报告

2021-02-27 约 1075 字预计阅读 3 分钟

Statement

传送门

一个 $n \times m$ 的网格，有 $K$ 个障碍格子，其余格子均可以放一个士兵。

求使得第 $i$ 行士兵数量大于等于 $L_i$ ，第 $j$ 列士兵数量大于等于 $C_i$ 时的最小士兵放置数量。

$n, m \le 100, K \le n \times m$ 。

Solution

这题有一个比较显然的上下界网络流解法：

对每一行 $i$ ，从源点 $S$ 向点 $i$ 连一条下界为 $L_i$ 的边；

对每一列 $j$ ，从 $n + j$ 向汇点 $T$ 连一条下界为 $C_i$ 的边；

对每一行 $i$ 以及每一列 $j$ ，如果格子 $(i,j)$ 不是障碍格子，则从 $i$ 向 $j$ 连一条上界为 $1$ 的边，表示在格子 $(i,j)$ 上放置一个士兵。

建完图后跑一个有源汇的上下界网络流即可。

但是我们会发现，这张图从 $S$ 连向 $1 \sim n$ 以及从 $n + 1 \sim n + m$ 连向 $T$ 的这些边都只有下界没有上界，那么我们是否可以对模型做一些改变，把下界改为上界，就可以使用普通最大流算法来解决这个问题了。

我们从逆向考虑这个问题。先假设一开始在所有的非障碍格子都放了一个士兵，然后接下来我们要计算的就是：在满足限制的情况下，最多能够删掉多少个士兵。

我们设 $totL_i$ 表示第 $i$ 行的非障碍格子数量， $totC_j$ 表示第 $j$ 列的非障碍格子数量。

对于每一行 $i$ ，从源点 $S$ 向点 $i$ 连一条容量为 $totL_i - L_i$ 的边；

对于每一行 $j$ ，从 $n + j$ 向汇点 $T$ 连一条容量为 $totC_i - C_i$ 的边；

对于每一行 $i$ 和每一行 $j$ ，从 $i$ 向 $n + j$ 连一条容量为 $1$ 的边。

在这张图上跑最大流算法，最终的答案就是 $n \times m - K - \mathrm{max\_flow}$ 。

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


#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int _ = 2e2 + 7;
const int __ = 2e4 + 7;
const int inf = 1e9;
const int S = 2e2 + 1, T = 2e2 + 2;

int n, m, K, L[_], C[_], totL[_], totC[_], maxflow;
bool b[_][_];
int dis[_], lst[_], cur[_], nxt[__], to[__], cap[__], tot = 1;
queue<int> q;

void Add(int x, int y, int c) {
  nxt[++tot] = lst[x], to[tot] = y, cap[tot] = c, lst[x] = tot;
  nxt[++tot] = lst[y], to[tot] = x, cap[tot] = 0, lst[y] = tot;
}

bool Bfs() {
  memset(dis, 0, sizeof dis);
  while (!q.empty()) q.pop();
  dis[S] = 1, q.push(S);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = lst[u]; i; i = nxt[i]) {
      int v = to[i];
      if (dis[v] or !cap[i]) continue;
      dis[v] = dis[u] + 1, q.push(v);
      if (v == T) return 1;
    }
  }
  return 0;
}

int Extend(int u, int flow) {
  if (u == T) return flow;
  int res = flow;
  for (int &i = cur[u]; i; i = nxt[i]) {
    int v = to[i];
    if (dis[v] != dis[u] + 1 or !cap[i]) continue;
    int cst = Extend(v, min(cap[i], res));
    cap[i] -= cst, cap[i ^ 1] += cst, res -= cst;
    if (!res) break;
  }
  return flow - res;
}

void Dinic() {
  int flow;
  while (Bfs()) {
    memcpy(cur, lst, sizeof cur);
    do {
      flow = Extend(S, inf);
      maxflow += flow;
    } while (flow);
  }
}

int main() {
  cin >> n >> m >> K;
  for (int i = 1; i <= n; ++i) cin >> L[i], totL[i] = m;
  for (int i = 1; i <= m; ++i) cin >> C[i], totC[i] = n;
  for (int i = 1, x, y; i <= K; ++i) {
    cin >> x >> y;
    if (!b[x][y]) b[x][y] = 1, --totL[x], --totC[y];
  }

  for (int i = 1; i <= n; ++i) {
    if (totL[i] < L[i]) { puts("JIONG!"); exit(0); }
    Add(S, i, totL[i] - L[i]);
  }
  for (int i = 1; i <= m; ++i) {
    if (totC[i] < C[i]) { puts("JIONG!"); exit(0); }
    Add(n + i, T, totC[i] - C[i]);
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      if (!b[i][j]) Add(i, n + j, 1);

  Dinic();
  cout << n * m - K - maxflow << endl;
  return 0;
}

Reference

题解 P4311 【士兵占领】 by GGN_2015。

目录

[解题报告][luoguP4311]士兵占领

Statement

Solution

Code

Reference