BZOJ4657 Tower <最小割>

Posted on Symbols count in article: 1.5k Reading time ≈ 6 mins.

Problem

Tower

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

Nick\mathrm{Nick}最近在玩一款很好玩的游戏，游戏规则是这样的：
有一个n×mn\times m的地图，地图上的每一个位置要么是空地，要么是炮塔，要么是一些BETA\mathrm{BETA}狗，Nick\mathrm{Nick}需要操纵炮塔攻击BETA\mathrm{BETA}狗们。
攻击方法是：对于每个炮塔，游戏系统已经给出它可以瞄准的方向（上下左右其中一个），Nick\mathrm{Nick}需要选择它的攻击位置，每一个炮塔只能够攻击一个位置，炮塔只能够向着它的瞄准方向上的某个位置发动攻击，当然炮塔也可以不进行攻击。炮塔威力强大，它可以且仅可以消灭目标位置上所有的BETA\mathrm{BETA}狗。
出于安全考虑，游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔，即对于任意一个炮塔，它所有可能的攻击位置上不存在另外一个炮塔。而且，如果把炮塔的起点和终点称为炮弹的运行轨迹，那么系统不允许两条轨迹相交（包括起点和终点）。
现在，选定目标位置以后，每一个炮塔同时开炮，你要告诉Nick\mathrm{Nick}，他最多可以干掉多少BETA\mathrm{BETA}狗。

Input

第一行两个正整数n,mn,m，表示地图的规模。
接下来礼行，每行mm个整数，00表示空地，−1,−2,−3,−4-1,-2,-3,-4分别表示瞄准上下左右的炮塔，若为正整数pp，则表示该位置有pp个BETA\mathrm{BETA}狗。

Output

一个正整数，表示Nick\mathrm{Nick}最多可以干掉几个BETA\mathrm{BETA}狗

Sample Input

1
2
3
4
3 2
0 9
-4 3
0 -1

Sample Output

1
9

HINT

n,m≤50n,m\le 50
每个位置的BETA\mathrm{BETA}狗数量不超过999999个
保证不存在任意一个炮塔能够瞄准另外一个炮塔

标签：最小割

Solution

经典最小割建模之一。

网格图可以拆成两个图，即所有行组成的图和所有列组成的图。这样原图中每个点变成两个，在行图上的称为行点，在列图上的称为列点。对于点ii，不妨设其行点为i1i_1，列点为i2i_2。

图上的向左或向右的炮将图分为若干横向的链，每个炮可以打到的区域都是一条链。在这个区域中，我们找出贡献最大的点ii，作为基础贡献，将此链上不所有同于ii的点jj的贡献pjp_j变为pi−pjp_i-p_j。对于每条链，我们从左往右或从右往左串联，连边k→k+1k\to k+1流量为kk点的新贡献，这样割掉这条边表示用这条链所对应的炮打kk的位置。如此，链被分为两段，从链首到kk为一段，从k+1k+1到链尾为另一段，符合割的定义。对于所有向上或向下的炮也如法炮制，只不过前者在行图上连，后者在列图上连。每个点的行点和列点间连流量为∞\infty的边，代表无法割断。

重新整理一下建图：
对于点ii，若

  • pi=−1或−2p_i=-1或-2
    • 连边S→i1S\to i_1流量为∞\infty
    • 对于其可以打到的链上的点kk，连边k1→k1+1k_1\to k_1+1流量为mx−pkmx-p_k，其中mxmx为此链上的最大pp值
  • pi=−3或−4p_i=-3或-4
    • 连边i2→Ti_2\to T流量为∞\infty
    • 对于其可以打到的链上的点kk，连边k2→k2+1k_2\to k_2+1流量为mx−pkmx-p_k，其中mxmx为此链上的最大pp值
  • pi≥0p_i\ge0，连边i1→i2i_1\to i_2流量为∞\infty

建模后跑最大流求最小割，答案为每条链的最大p值之和−最小割每条链的最大p值之和-最小割。

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
#include <bits/stdc++.h>
#define MAX_N 5000
#define MAX_M 600000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, tot, mp[55][55];
int d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5];
int pos(int x, int y, int id) {return n*m*(id-1)+(x-1)*m+y;}
void init() {s = 0, t = n*m*2+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que; que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow; int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = s; i <= t; i++) cr[i] = pr[i];}
void rec() {for (int i = s; i <= t; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0; cpy(); while (BFS()) ret += DFS(s, INF), rec(); return ret;}
int main() {
    read(n), read(m), init();
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) read(mp[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1, mx = 0; j <= m; j++, tot += mx, mx = 0)
            if (mp[i][j] == -1) {
                addedge(s, pos(i, j, 1), INF);
                for (int k = i; k >= 1; k--) mx = max(mx, max(mp[k][j], 0));
                for (int k = i; k > 1; k--)
                    addedge(pos(k, j, 1), pos(k-1, j, 1), mx-max(mp[k][j], 0));
            } else if (mp[i][j] == -2) {
                addedge(s, pos(i, j, 1), INF);
                for (int k = i; k <= n; k++) mx = max(mx, max(mp[k][j], 0));
                for (int k = i; k < n; k++)
                    addedge(pos(k, j, 1), pos(k+1, j, 1), mx-max(mp[k][j], 0));
            } else if (mp[i][j] == -3) {
                addedge(pos(i, j, 2), t, INF);
                for (int k = j; k >= 1; k--) mx = max(mx, max(mp[i][k], 0));
                for (int k = j; k > 1; k--)
                    addedge(pos(i, k-1, 2), pos(i, k, 2), mx-max(mp[i][k], 0));
            } else if (mp[i][j] == -4) {
                addedge(pos(i, j, 2), t, INF);
                for (int k = j; k <= m; k++) mx = max(mx, max(mp[i][k], 0));
                for (int k = j; k < m; k++)
                    addedge(pos(i, k+1, 2), pos(i, k, 2), mx-max(mp[i][k], 0));
            } else addedge(pos(i, j, 1), pos(i, j, 2), INF);
    return printf("%d\n", tot-Dinic()), 0;
}