subject

P2472 [SCOI2007] lizard

analysis

The idea of this problem is quite clear. In this paper, I ran the maximum flow with Jiu as my brain free map, but I hung up and rebuilt the map after an hour.

Build a super source and a super sink,
Every stone pillar has its fixed passing times, that is to say, we need to limit its passing times. How to limit it? Dismantle the points, divide each point with a stone pillar into two, and the connected side flow is its height, so as to limit its passing times
For \ ((i,j) \) location

1. If there is a stone column, connect one \ ((I, J) - > (I, J) + n \ times C \), and the flow is the edge of the height of the stone column, indicating that the stone column can pass several times
2. If there i s a lizard, connect a \ (s - > (I, J) \) side with a flow of \ (1 \) to represent this lizard
3. If there is a stone column \ ((x,y) \), connect one \ ((I, J) + n \ times C - > (x,y) \), and the flow is \ (INF \)
4. If i t can be out of bounds, connect one side of \ ((I, J) - > t \) whose traffic is \ (INF \)

In the latter two cases, the edge only serves as a connection, so the traffic is \ (INF \)

Note: the latter three are all carried out under the condition of satisfying the first one.
Through the above mapping method, we can find out the lizards that can go out of the boundary, and then we can use the total number of lizards \ (\) to escape the number of lizards is the final answer.

It's not hard to think, it's a lot of trouble to build maps.

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n, c, d, s, t, sum, num = 1;
int head[N], cur[N], dep[N];
int a[50][50];
char S[50];
class node {
    public :
        int v, nx, w;
} e[N];

template<class T>inline void read(T &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return;
}

int bian_hao(int i, int j) {
    return (i - 1) * c + j;
}

inline void add(int u, int v, int w) {
    e[++num].nx = head[u], e[num].v = v, e[num].w = w, head[u] = num;
    e[++num].nx = head[v], e[num].v = u, e[num].w = 0, head[v] = num;
}

queue<int>q;
bool bfs() {
    memset(dep, 0, sizeof dep);
    memcpy(cur, head, sizeof cur);
    dep[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = e[i].nx) {
            int v = e[i].v;
            if (e[i].w && !dep[v]) dep[v] = dep[u] + 1, q.push(v);
        }
    }
    return dep[t];
}

int dfs(int u, int flow) {
    if (u == t) return flow;
    int use = 0;
    for (int &i = cur[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (e[i].w && dep[v] == dep[u] + 1) {
            int di = dfs(v, min(flow, e[i].w));
            e[i].w -= di, e[i ^ 1].w += di;
            use += di, flow -= di;
            if (flow <= 0) break;
        }           
    } 
    return use;
}

int dinic() {
    int ans = 0;
    while (bfs()) ans += dfs(s, INF);
    return ans;
}

int main() {
    memset(head, -1, sizeof head);
    read(n), read(c), read(d);
    s = (n * c) * 3 + 1, t = s + 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%s", S + 1);
        for (int j = 1; j <= c; ++j) {
            a[i][j] = S[j] - '0';
            if (a[i][j]) {
                add(bian_hao(i, j), bian_hao(i, j) + n * c, a[i][j]);   //Stone pillars 
                if (i <= d || i >= n - d + 1 || j <= d || j >= c - d + 1) add(bian_hao(i, j) + n * c, t, INF);  //Out of bounds 
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%s", S + 1);
        for (int j = 1; j <= c; ++j) if (S[j] == 'L') 
            add(s, bian_hao(i, j), 1), sum++;           //Lizards 
    }
    for (int dx = -d; dx <= d; ++dx)
        for (int dy = -d; dy <= d; ++dy) {
            if (dx * dx + dy * dy > d * d) continue;
            for (int i = 1; i <= n; ++i) 
                for (int j = 1; j <= c; ++j) {
                    int x = i + dx, y = j + dy;
                    if (x < 1 || x > n || y < 1 || y > c || !a[i][j]) continue;
                    add(bian_hao(i, j) + n * c, bian_hao(x, y), INF);           //Can reach other stone pillars 
                }
        }
    printf("%d\n", sum - dinic());
}