[SCOI2007] 蜥蜴

1 题目背景与分析

题目大意：给定一个网格图，每个格子上有一个石柱，高度不一。蜥蜴在石柱间跳跃，每次跳跃离开时，脚下的石柱高度减 1。当高度为 0 时石柱消失。求最少有多少只蜥蜴无法逃出网格边界。

这道题初看似乎是一个复杂的动态规划或者搜索问题，但仔细分析会发现以下特征：

资源限制：每个石柱有使用次数上限（即高度）。
流动性：蜥蜴从一个点转移到另一个点。
目标：最大化逃出的数量（题目问最少留下的，即 总数 - 最大逃出数）。

这非常符合网络最大流的模型！

2 建图难点：如何限制“点”的流量？

在标准的网络流问题中，我们通常限制边（Edge）的容量。但是在这道题中，限制在于点（石柱）本身——一个高度为 3 的石柱最多只能被踩 3 次。

这时候我们需要用到拆点（Vertex Splitting）技巧。

拆点法

我们将网格中的每一个坐标 $(r, c)$ 拆分成两个逻辑节点：

入点 (In-node)：接受来自其他石柱的跳跃。
出点 (Out-node)：负责向其他石柱发起跳跃。

在这两个点之间连一条边：In -> Out。

容量：等于该石柱的初始高度 $h_{i,j}$ 。
意义：这就把“点的通过次数限制”转化为了“边的流量限制”。

3 详细构图方案

设超级源点为 $S$ ，超级汇点为 $T$ 。

源点连接 (蜥蜴出发)：
- 如果有蜥蜴在 $(r, c)$ ，连接 $S \to (r, c)_{in}$ ，容量为 1。
- 表示每只蜥蜴是一个单位的流量。
石柱自身限制 (拆点)：
- 对于每个有石柱的点，连接 $(r, c)_{in} \to (r, c)_{out}$ ，容量为 $h_{i,j}$ 。
石柱间跳跃 (移动)：
- 如果石柱 A 和石柱 B 的欧几里得距离 $dist(A, B) \leq d$ ，连接 $A_{out} \to B_{in}$ 。
- 容量为 $\infty$ （因为只要石柱没塌，跳跃路径本身没有限制）。
逃生 (到达汇点)：
- 如果石柱 $(r, c)$ 能直接跳出地图边界（即 $r \leq d$ 或 $r > R-d$ 或 $c \leq d$ 或 $c > C-d$ ），连接 $(r, c)_{out} \to T$ 。
- 容量为 $\infty$ 。

4 节点编号原理

二维网格上的每个格子,拆成2个点,下面是一个 $3 \times 3$ 每个格子对应的in,out 编号

( 1 , 10 )  ( 2 , 11 )  ( 3 , 12 )  
( 4 , 13 )  ( 5 , 14 )  ( 6 , 15 )  
( 7 , 16 )  ( 8 , 17 )  ( 9 , 18 )

我们将二维坐标 $\left(r,c\right)$ 按照**“从左到右，从上到下”**的顺序“压扁”为一维编号。

假设网格规模为 $R$ 行 $C$ 列，总点数 $N=R\times C$ ：

In 点编号（基础层） 原理：先算上面有几行完整格子，再加当前是第几个。
$ID_{in}=\left(r-1\right)\times C+c$
Out 点编号（拆点层） 原理：在 In 点编号的基础上，统一加上总点数偏移量。
$ID_{out}=ID_{in}+N$

示例验证（以 $3\times 3$ 网格的中心点 $\left(2,2\right)$ 为例）：

$C=3,N=9$
In 点：上面有 1 行完整格子， $\left(2-1\right)\times 3+2=5$
Out 点： $5+9=14$
对应编号： $\left(5,14\right)$

5 如何计算距离d

简单来说，这里的“平面距离”指的就是我们在几何学中最常见的欧几里得距离（Euclidean Distance），也就是两点之间直线的长度。

因为蜥蜴是“跳”过去的，不是沿着网格走的（那叫曼哈顿距离），所以它是走直线的。

1. 数学定义

假设蜥蜴现在的坐标是 $(r_1, c_1)$ ，它想跳到的石柱坐标是 $(r_2, c_2)$ 。

那么它们之间的平面距离公式是：

\text{距离} = \sqrt{(r_1 - r_2)^2 + (c_1 - c_2)^2}

题目要求是：距离 $\le d$ 。

2. 代码实现技巧（重点）

在写代码时，为了避免使用 sqrt() 开根号导致浮点数精度误差（比如算出 1.999999… 导致判定错误），我们通常会把公式两边同时平方。

判定条件改为：

(r_1 - r_2)^2 + (c_1 - c_2)^2 \le d^2

这样所有的计算都是整数运算，既快又准。

3. 举个例子

假设 $d = 2$ （最大跳跃距离是 2）。

蜥蜴在 $(1, 1)$ 。

目标 A $(1, 3)$ ：
- 行差： $1-1=0$ ，列差： $1-3=-2$ 。
- 距离平方： $0^2 + (-2)^2 = 4$ 。
- $d^2 = 2^2 = 4$ 。
- 因为 $4 \le 4$ ，所以能跳到。
目标 B $(2, 3)$ ：
- 行差： $1-2=-1$ ，列差： $1-3=-2$ 。
- 距离平方： $(-1)^2 + (-2)^2 = 1 + 4 = 5$ 。
- 因为 $5 > 4$ ，所以跳不到（实际距离是 $\sqrt{5} \approx 2.23$ ）。

在你的代码中

对应代码中的 distSq 函数：

C++

// 计算两点距离平方
int distSq(int r1, int c1, int r2, int c2) {
    return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}

// 判定时：
if (distSq(r1, c1, r2, c2) <= D * D) { 
    // ... 连边 ...
}

6 算法流程

读入数据，计算初始蜥蜴总数 cnt。
按照上述方案构建 Dinic 网络流图。
跑一遍 maxFlow(S, T)，得到最大逃生数量 max_escape。
答案即为 cnt - max_escape。

7 核心代码解析 (C++ based on Dinic Template)

cpp

// 核心建图逻辑
for(int i = 1; i <= R; i++) {
    for(int j = 1; j <= C; j++) {
        // ...读取高度 h ...
        if (h > 0) {
            // 1. 拆点限制容量
            dinic.addEdge(getInId(i, j), getOutId(i, j), h);

            // 2. 处理逃生
            if (can_jump_out(i, j, D, R, C)) {
                dinic.addEdge(getOutId(i, j), t, INF); 
            }
        }
    }
}

// ... 处理蜥蜴位置和石柱间连边 ...

8 总结

这道题是练习拆点技巧的绝佳入门题。当我们遇到“节点有通过次数限制”或“节点有权值”的网络流题目时，第一时间就应该想到把一个点拆成两个，中间连一条边来控制容量。

给你的建议 (Next Step): 你对图论的理解已经非常深入了。既然你已经掌握了 Dinic 和拆点技巧，下一步你可以尝试解决 P3355 [骑士共存问题]。那道题是二分图最大匹配，也可以用最大流解决，需要结合棋盘染色的思想，非常有趣！你想试试吗？

9 代码实现

我保留了你的 linkList 和 Dinic 结构体几乎原封不动（因为它们已经很完美了），主要是在 main 函数中进行了建模。

修改重点：

拆点：因为限制条件是“石柱的高度”，也就是点的容量限制，所以要把每个坐标 $(r, c)$ 拆成两个点：In点 和 Out点。连边 In -> Out，容量为石柱高度。
源点连边：如果有蜥蜴，S -> In点，容量为 1。
跳跃连边：如果两根石柱距离 $e d$ ，从 $A$ 的 Out点 连向 $B$ 的 In点，容量 $nfty$ 。
汇点连边：如果某石柱能跳出地图边界，从该石柱的 Out点 连向 T，容量 $nfty$ 。

cpp

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+5; // 点数足够大
const int maxe = 2e6+5; // 边数足够大

// 存图的模板 
struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn], edge_cnt=0;
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w);
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    
    edge& operator[](int i){ return e[i]; }
    int operator()(int u){ return h[u]; }
} e;

// Dinic算法模板 
struct Dinic {
    vector<int> level, iter;
    int n; 
    
    Dinic(int n) : n(n), level(n+5), iter(n+5) {
        e.edge_cnt = 0;
        memset(e.h, -1, sizeof(e.h));
    }
    
    void addEdge(int u, int v, long long cap) {
        e.add(u, v, cap);
        e.add(v, u, 0);
    }
    
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            e.for_each(u, [&](int from, int to, int cap) {
                if (cap > 0 && level[to] < 0) {
                    level[to] = level[u] + 1;
                    q.push(to);
                }
            });
        }
        return level[t] >= 0;
    }
    
    long long dfs(int u, int t, long long preFlow) {
        if (u == t || preFlow == 0) return preFlow;
        long long flow = 0;
        
        for (int& cid = iter[u]; cid != -1; cid = e[cid].next) {
            auto& edge = e[cid];
            int to = edge.v;
            long long cap = edge.w;
            
            if (level[u] + 1 != level[to] || cap <= 0) continue;
            
            long long tr = dfs(to, t, min(preFlow, cap));

            e[cid].w -= tr;
            e[cid ^ 1].w += tr;
            flow += tr;
            preFlow -= tr;
            if (preFlow == 0) break;
        }
        
        if (flow == 0) level[u] = -1;
        return flow;
    }
    
    long long maxFlow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            for (int i = 0; i <= n; i++) {
                iter[i] = e(i);
            }
            flow += dfs(s, t, LLONG_MAX);
        }
        return flow;
    }
};

// --- P2472 专用逻辑 ---

int R, C, D;
char grid_h[25][25]; // 石柱高度
char grid_l[25][25]; // 蜥蜴位置

// 辅助函数：计算两点距离平方
int distSq(int r1, int c1, int r2, int c2) {
    return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}

// 辅助函数：将二维坐标转换为节点编号
// 每个坐标 (i, j) 拆分为两个点：
// In点编号: (i-1)*C + j
// Out点编号: (i-1)*C + j + (R*C)
int getInId(int r, int c) { return (r - 1) * C + c; }
int getOutId(int r, int c) { return getInId(r, c) + (R * C); }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    if (!(cin >> R >> C >> D)) return 0;

    int total_nodes = 2 * R * C + 2;
    int s = 0; 
    int t = total_nodes - 1; // 汇点设为最大的编号

    Dinic dinic(total_nodes);

    int lizard_count = 0;

    // 1. 读取石柱高度
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) {
            cin >> grid_h[i][j];
            int h = grid_h[i][j] - '0';
            
            // 如果有石柱 (高度 > 0)
            if (h > 0) {
                // 核心技巧：拆点。 In -> Out，容量为石柱高度
                dinic.addEdge(getInId(i, j), getOutId(i, j), h);

                // 如果这个石柱可以直接跳出边界 (逃生)
                // 距离判断：行 < 1 或 > R，列 < 1 或 > C 的逻辑转换
                // 也就是：如果当前坐标 r <= D 或 r > R - D ...
                // 为什么这样计算: 相当于绘制一个半径为d的圆
                if (i <= D || i > R - D || j <= D || j > C - D) {
                    dinic.addEdge(getOutId(i, j), t, 1e9); // 容量无限
                }
            }
        }
    }

    // 2. 读取蜥蜴位置并构建源点边
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) {
            cin >> grid_l[i][j];
            if (grid_l[i][j] == 'L') {
                lizard_count++;
                // 源点 -> 蜥蜴所在的石柱(In点)，容量 1
                dinic.addEdge(s, getInId(i, j), 1);
            }
        }
    }

    // 3. 构建石柱之间的跳跃边
    // 枚举两个石柱 u 和 v
    for(int r1 = 1; r1 <= R; r1++) {
        for(int c1 = 1; c1 <= C; c1++) {
            if (grid_h[r1][c1] == '0') continue; // 没有石柱不能跳

            for(int r2 = 1; r2 <= R; r2++) {
                for(int c2 = 1; c2 <= C; c2++) {
                    if (r1 == r2 && c1 == c2) continue; // 是同一个点
                    if (grid_h[r2][c2] == '0') continue; // 目标没石柱

                    // 如果距离允许跳跃
                    if (distSq(r1, c1, r2, c2) <= D * D) {
                        // 从 (r1,c1) 的 Out 跳到 (r2,c2) 的 In
                        dinic.addEdge(getOutId(r1, c1), getInId(r2, c2), 1e9);
                    }
                }
            }
        }
    }

    // 4. 计算最大流
    // 最大流 = 能逃跑的最大蜥蜴数量
    long long escaped = dinic.maxFlow(s, t);

    // 题目要求输出：无法逃离的蜥蜴数量
    cout << lizard_count - escaped << "";

    return 0;
}

目录