P2472 [SCOI2007]蜥蜴 (最大流)

題目

P2472 [SCOI2007]蜥蜴

解析

這個題思路比較清晰，本(qi)來(shi)以(jiu)為(shi)無腦建圖跑最大流，結果掛了，整了一個小時後重新建圖才過的。

建立一個超級源點和一個超級匯點，
每個石柱都有其固定的通過的次數，也就是說我們要限制其通過次數，怎麼限制呢，拆點，把每個有石柱的點拆成兩個，相連的邊流量為其高度，這樣就做到了限制其通過次數
對於\((i,j)\)位置

1. 如果有石柱，連一條\((i,j)->(i,j)+n\times c\)，流量為石柱高度的邊，來表示石柱可以通過幾次
2. 如果有蜥蜴，連一條\(s->(i,j)\)，流量為\(1\)的邊，來表示這一隻蜥蜴
3. 如果有能到達的石柱\((x,y)\)，連一條\((i,j)+n\times c -> (x,y)\)，流量為\(INF\)的邊
4. 如果能出界，連一條\((i,j)->t\)的流量為\(INF\)的邊

後兩種情況的邊只是起連接作用，所以流量為\(INF\).

註意：後面三條都是在滿足第一條的條件下進行的。
通過上面的建圖方法，我們就求出了可以出界的蜥蜴，然後我們用蜥蜴的總數\(-\)可以逃出的蜥蜴數就是最後的答案。

思路不難，就是建圖麻煩的一批。

代碼

#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]);   //有石柱 
                if (i <= d || i >= n - d + 1 || j <= d || j >= c - d + 1) add(bian_hao(i, j) + n * c, t, INF);  //可以出界 
            }
        }
    }
    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++;           //有蜥蜴 
    }
    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);           //能到別的石柱 
                }
        }
    printf("%d\n", sum - dinic());
}