BZOJ1066【SCOI2007】蜥蜴 <网络流>

Posted on Symbols count in article: 814 Reading time ≈ 3 mins.

Problem

【SCOI2007】蜥蜴

Description

在一个rr行cc列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为11，蜥蜴的跳跃距离是dd，即蜥蜴可以跳到平面距离不超过dd的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减11（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为11，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。

Input

输入第一行为三个整数rr，cc，dd，即地图的规模与最大跳跃距离。以下rr行为石竹的初始状态，00表示没有石柱，1∼31\sim 3表示石柱的初始高度。以下rr行为蜥蜴位置，“LL”表示蜥蜴，“..”表示没有蜥蜴。

Output

输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........

Sample Output

1
1

HINT

100%100\%的数据满足：1≤r,c≤201\le r, c\le 20, 1≤d≤41\le d\le 4

标签：网络流

Solution

简单的拆点建模题。
从源点向每个有蜥蜴的点连容量为11的边，从每个能跳出去的点向汇点连容量为∞\infty的边。对于石笋高度，把每个点拆成两个点，它们间的边容量为石笋高度，若位置(i,j)(i, j)可跳到(p,q)(p, q)，则从(i,j)(i, j)的第二个点向(p,q)(p, q)的第一个点连容量为∞\infty的边。最后跑最大流即可。
点数少，都懒得用边表了，直接用邻接矩阵

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 20
#define INF 2147483647
using namespace std;
int n, m, r, s, t, cnt, tot, id[MAX_N+5][MAX_N+5], map[MAX_N*MAX_N*2+5][MAX_N*MAX_N*2+5];
char a[MAX_N+5][MAX_N+5], b[MAX_N+5][MAX_N+5];
void build(int x, int y) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if ((i != x || j != y) && (a[i][j] != '0') && r*r >= (x-i)*(x-i)+(y-j)*(y-j))
                map[id[x][y]+1][id[i][j]] = INF;
}
int d[MAX_N*MAX_N*2+5];
bool BFS() {
    queue <int> que;
    memset(d, -1, sizeof(d));
    d[s] = 0, que.push(s);
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int v = 0; v <= cnt; v++) {
            if (d[v] != -1 || !map[u][v])	continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return d[t] != -1;
}
int DFS(int u, int flow) {
    if (u == t)	return flow;	int ret = 0;
    for (int v = 0; v <= cnt; v++) {
        if (d[v] != d[u]+1 || !map[u][v])	continue;
        int tmp = DFS(v, min(flow, map[u][v]));
        map[u][v] -= tmp, map[v][u] += tmp, flow -= tmp, ret += tmp;
        if (!flow)	break;
    }
    if (!ret)	d[u] = -1;
    return ret;
}
int Dinic() {
    int ret = 0;
    while (BFS())	ret += DFS(s, INF);
    return ret;
}
int main() {
    scanf("%d%d%d", &n, &m, &r);
    for (int i = 1; i <= n; i++) {
        scanf("%s", a[i]+1);
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '0')	continue;
            id[i][j] = cnt+1, map[cnt+1][cnt+2] = a[i][j]-'0', cnt += 2;
        }
    }
    s = 0, t = ++cnt;
    for (int i = 1; i <= n; i++) {
        scanf("%s", b[i]+1);
        for (int j = 1; j <= m; j++) {
            if (b[i][j] == 'L')	tot++, map[s][id[i][j]] = 1;
            if (i-r < 1 || i+r > n || j-r < 1 || j+r > m)	map[id[i][j]+1][t] = INF;
            if (a[i][j] != '0')	build(i, j);
        }
    }
    printf("%d", tot-Dinic());
    return 0;
}