「BZOJ 4261」建设游乐场

发表于 | 分类于

Description

给定一个\(n\times m\)网格图，其中有一些点是障碍，有一些点是平原。

现在要求你用若干无重边无自环的不相交简单环覆盖所有平原。有一些点\((i, j)\)如果满足经过的两条边一条是横着的一套是竖着的那么就会获得\(V_{i, j}\)的收益。

求是否有解，如果有解的话输出最大收益。

\(n\le 150\)，\(m\le 30\)，\(0\le V_{i, j}\le 100\)。

Solution

算是坑了很久的传统艺能题，，，

首先先来一步传统艺能：假设所有收益都能获得，然后问题转化成使笋丝尽可能小，也就变成了如果有一个地方是直的话就会有笋丝。

考虑黑白染色，我们钦点只从黑点往白点连边，这样的话每个黑点要向两个不同的白点（不能走到障碍上）连边。我们要希望所有点都弯着走，我们大可以把所有点全部拆成两个点，一个表示横着走一个表示竖着走，分别向源/汇连容量为1的边，同时他们再往相邻的横着/竖着相邻的点连容量为1的边。

但问题是有些时候有些点肯定只能直着走。那可以用“弯直转换”来表示，具体方法就是把一个点拆出来的横竖点互连容量为1费用为\(V_{i, j}\)的边。

最后关于是否有解的判定……最后的流量就是原网格图中用了的边的数量，对于每个环的边数都等于点数，因此总边数要等于总点数，因此最后的流量要等于平地的总数量才算有解。

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
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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
const int maxn = (150 * 30) * 2 + 5;
struct Edge {
  int u, v, cap, flow, cost;
};

std::vector<int> G[maxn];
std::vector<Edge> E;
inline void add_edge(int u, int v, int cap, int cost) {
  E.push_back((Edge){u, v, cap, 0, cost});
  E.push_back((Edge){v, u, 0, 0, -cost});
  int m = E.size();
  G[u].push_back(m - 2); G[v].push_back(m - 1);
}

int a[maxn], d[maxn], p[maxn];
bool inq[maxn];
int num;
const int INF = 0x3f3f3f3f;
inline bool spfa(int s, int t, int &flow, int &cost) {
  std::fill(a, a + num + 1, 0);
  std::fill(d, d + num + 1, INF);
  std::fill(p, p + num + 1, 0);
  std::fill(inq, inq + num + 1, false);
  std::queue<int> Q; Q.push(s);
  d[s] = 0; a[s] = INF; inq[s] = true;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop(); inq[u] = false;
    for(int i = 0; i < G[u].size(); i ++) {
      Edge &e = E[G[u][i]]; int v = e.v;
      if(e.cap > e.flow && d[u] + e.cost < d[v]) {
        d[v] = d[u] + e.cost; p[v] = G[u][i];
        a[v] = std::min(a[u], e.cap - e.flow);
        if(!inq[v]) Q.push(v), inq[v] = true;
      }
    }
  }
  if(d[t] >= INF) return false;
  flow += a[t]; cost += d[t] * a[t];
#ifdef LOCAL
  printf("flow delta : %d\n", a[t]);
  printf("cost delta : %d\n", d[t] * a[t]);
#endif
  int u = t;
  while(u != s) {
    Edge &e = E[p[u]];
    e.flow += a[t]; E[p[u] ^ 1].flow -= a[t];
    u = e.u;
  }
  return true;
}
inline void MCMF(int s, int t, int &flow, int &cost) {
  while(spfa(s, t, flow, cost));
}

int n, m;
inline int get_p(int i, int j, int t) {
  int ret = (i - 1) * m + j;
  ret = ret * 2 - 1 + t;
  return ret;
}

int A[155][35], V[155][35];
int main() {
  scanf("%d%d", &n, &m);
  int s = 0, t = n * m * 2 + 1; num = t;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      scanf("%d", &A[i][j]);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      scanf("%d", &V[i][j]);
      if(!A[i][j]) ans += V[i][j];
    }
  }
  
  int cnt = 0;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      if(A[i][j]) continue;
      cnt ++; int p0 = get_p(i, j, 0), p1 = get_p(i, j, 1);
      add_edge(p0, p1, 1, V[i][j]); add_edge(p1, p0, 1, V[i][j]);
      if((i + j) & 1) {
        add_edge(p0, t, 1, 0); add_edge(p1, t, 1, 0);
      } else {
        add_edge(s, p0, 1, 0); add_edge(s, p1, 1, 0);
        if(i > 1 && !A[i - 1][j]) {
          add_edge(p0, get_p(i - 1, j, 0), 1, 0);
        }
        if(i < n && !A[i + 1][j]) {
          add_edge(p0, get_p(i + 1, j, 0), 1, 0);
        }
        if(j > 1 && !A[i][j - 1]) {
          add_edge(p1, get_p(i, j - 1, 1), 1, 0);
        }
        if(j < m && !A[i][j + 1]) {
          add_edge(p1, get_p(i, j + 1, 1), 1, 0);
        }
      }
    }
  }
#ifdef LOCAL
  printf("tot : %d\n", ans);
#endif
  int flow = 0, cost = 0;
  MCMF(s, t, flow, cost);
  if(flow < cnt) {
    puts("-1");
  } else {
    printf("%d\n", ans - cost);
  }
  return 0;
}