2676. 「BalticOI 2010」BEARs 题解

问题分析

我们有一个无限的网格城市，Wolf 要从 BEAR 的起点 $(A,B)$ 开始追赶，每次 BEAR 到达一个路口时，Wolf 可以封锁该路口四条道路中的一条（但不能封锁与主街道相连的道路）。Wolf 的目标是让 BEAR 能到达的所有点都满足 $\max(|x|, |y|) \ge D$，即 BEAR 无法进入以原点为中心、边长为 $2D$ 的正方形区域 $R_D = \{(x,y) : \max(|x|, |y|) < D\}$。

我们需要找到最大的 $D$，使得 Wolf 能通过适当的封锁策略阻止 BEAR 进入 $R_D$。

---

关键观察

1. 问题转化

这实际上是一个追逐-封锁游戏：

• BEAR 从 $(A,B)$ 出发，试图到达 $R_D$
• Wolf 在每个路口可以删除一条出边（不能删除主街道）
• 问 Wolf 能否阻止 BEAR 进入 $R_D$

2. 网络流模型

我们可以将问题转化为最小割问题：

• 每个路口是一个节点
• 每条道路是一条边（双向）
• Wolf 在每个路口可以删除一条出边 ⇔ 每个节点有容量限制

但注意：Wolf 在每个路口只能封锁一条道路，而不是删除所有出边。

3. 菱形区域性质

距离函数 $\max(|x|, |y|)$ 定义了一个菱形区域（实际上是正方形，但旋转45度后是菱形）。对于给定的 $D$，区域 $R_D$ 是：

$$R_D = \{(x,y) : -D < x < D, -D < y < D\}$$

我们需要阻止 BEAR 到达这个区域。

---

算法思路

方法一：二分答案 + 最大流验证

1. 二分框架

def solve():
    A, B = 读入起点
    N = 读入主街道数
    main_streets = 读入主街道列表
    
    left, right = 0, max(abs(A), abs(B)) + 1
    while left < right:
        mid = (left + right + 1) // 2
        if can_block(mid, A, B, main_streets):
            left = mid
        else:
            right = mid - 1
    
    return left

2. 验证函数 can_block(D, A, B, main_streets)

对于给定的 $D$，我们需要判断 Wolf 是否能阻止 BEAR 进入 $R_D$。

建模为最大流问题：

1. 节点：每个路口 $(x,y)$，但只需要考虑相关区域

   • 由于 Wolf 要保护 $R_D$，我们关心从 $(A,B)$ 到 $R_D$ 的路径
   • 可以限制在边界框内：$x \in [\min(A,-D)-1, \max(A,D)+1]$，$y$ 同理

2. 边：

   • 对于普通道路：双向边，容量为 1（Wolf 可以从两个方向封锁）
   • 对于主街道：容量为 INF（Wolf 不能封锁）

3. 特殊处理：

   • Wolf 在每个路口只能封锁一条道路 ⇔ 每个节点有出度限制
   • 这可以通过节点拆点实现：将每个路口拆分为入点和出点，中间边容量为 1

4. 源点和汇点：

   • 源点：BEAR 的起点 $(A,B)$
   • 汇点：将 $R_D$ 的所有边界点连接到一个超级汇点

5. 判断：

   • 如果从源点到汇点的最大流 ≥ 某个值，说明 BEAR 有足够路径可以到达 $R_D$
   • 但实际上，我们只需要判断是否存在路径
   • 更准确：如果最小割的容量有限，说明 Wolf 能封锁

---

详细建模

1. 图构建

struct Point {
    int x, y;
    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
    
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

struct Edge {
    Point from, to;
    bool is_main;  // 是否是主街道
};

2. 节点编号映射

由于网格可能很大，我们需要离散化坐标或使用哈希映射。

map<Point, int> point_to_id;
vector<Point> id_to_point;
int get_id(const Point& p) {
    if (point_to_id.find(p) == point_to_id.end()) {
        point_to_id[p] = id_to_point.size();
        id_to_point.push_back(p);
    }
    return point_to_id[p];
}

3. 网络流图构建

对于给定的 $D$：

// 构建网络流图
int n_nodes = 0;
// 1. 收集所有相关点
set<Point> points;
points.insert(Point(A, B));  // 起点

// 添加R_D的边界点
for (int x = -D; x <= D; x++) {
    points.insert(Point(x, -D));
    points.insert(Point(x, D));
}
for (int y = -D; y <= D; y++) {
    points.insert(Point(-D, y));
    points.insert(Point(D, y));
}

// 添加与主街道相关的点
for (auto& street : main_streets) {
    int x1 = street.x1, y1 = street.y1;
    int x2 = street.x2, y2 = street.y2;
    if (x1 == x2) {  // 垂直街道
        for (int y = min(y1, y2); y <= max(y1, y2); y++) {
            points.insert(Point(x1, y));
        }
    } else {  // 水平街道
        for (int x = min(x1, x2); x <= max(x1, x2); x++) {
            points.insert(Point(x, y1));
        }
    }
}

// 为每个点分配ID
for (auto& p : points) {
    get_id(p);
}
n_nodes = id_to_point.size();

// 2. 构建网络流图（使用Dinic算法）
// 每个点拆分为入点和出点：节点i的入点为2*i，出点为2*i+1
int total_nodes = 2 * n_nodes + 2;
int source = 2 * get_id(Point(A, B)) + 1;  // 起点的出点
int sink = 2 * n_nodes;  // 超级汇点

// 初始化图
vector<vector<Edge>> graph(total_nodes);

// 3. 添加内部边（节点容量限制）
for (int i = 0; i < n_nodes; i++) {
    int in_node = 2 * i;
    int out_node = 2 * i + 1;
    // 内部边容量为1：Wolf在每个路口只能封锁一条路
    add_edge(graph, in_node, out_node, 1);
}

// 4. 添加道路边
vector<Edge> all_edges;
// 收集所有可能的道路
for (auto& p : points) {
    int id = get_id(p);
    
    // 四个方向
    vector<Point> neighbors = {
        Point(p.x+1, p.y),  // 东
        Point(p.x-1, p.y),  // 西
        Point(p.x, p.y+1),  // 北
        Point(p.x, p.y-1)   // 南
    };
    
    for (auto& np : neighbors) {
        if (points.find(np) != points.end()) {
            int nid = get_id(np);
            
            // 检查是否是主街道
            bool is_main = false;
            for (auto& street : main_streets) {
                if (is_on_street(p, np, street)) {
                    is_main = true;
                    break;
                }
            }
            
            // 添加边：从p的出点到np的入点
            all_edges.push_back({p, np, is_main});
        }
    }
}

// 添加边到网络流图
for (auto& e : all_edges) {
    int from_id = get_id(e.from);
    int to_id = get_id(e.to);
    
    int from_node = 2 * from_id + 1;  // 出点
    int to_node = 2 * to_id;          // 入点
    
    // 主街道容量为INF，普通道路容量为1
    int capacity = e.is_main ? INF : 1;
    add_edge(graph, from_node, to_node, capacity);
}

// 5. 连接R_D的边界点到汇点
for (int x = -D; x <= D; x++) {
    for (int y = -D; y <= D; y++) {
        if (max(abs(x), abs(y)) == D) {  // 在边界上
            Point p(x, y);
            if (points.find(p) != points.end()) {
                int id = get_id(p);
                int in_node = 2 * id;  // 入点
                add_edge(graph, in_node, sink, INF);
            }
        }
    }
}

// 6. 运行最大流
int max_flow = dinic(source, sink, graph);

// 7. 判断：如果最大流有限，说明Wolf能封锁
// 实际上，如果最小割的容量小于某个值...
// 更简单：如果从起点到R_D的路径都需要经过某些关键点，且Wolf能封锁这些点

---

简化算法：平面图对偶

由于是网格图，我们可以用更简单的方法。平面图的对偶图性质：

1. 对偶图思想

• 原图的区域 ⇔ 对偶图的节点
• 原图的边 ⇔ 对偶图的边
• Wolf封锁一条边 ⇔ 切断对偶图的一条边

2. 具体实现

对于网格图，我们可以考虑从 $(A,B)$ 到 $R_D$ 的路径形成的切割。

Wolf 要阻止 BEAR 进入 $R_D$，相当于要在 $(A,B)$ 和 $R_D$ 之间建立一个屏障。这个屏障由封锁的道路组成。

由于 Wolf 在每个路口只能封锁一条路，这相当于每个路口最多贡献一条边到屏障。

3. 转化为最小割

实际上，这个问题可以转化为：

• 源点：$(A,B)$
• 汇点：$R_D$ 的外部（无穷远）
• 每条边的容量：Wolf 能否封锁（主街道为 INF，普通为 1）
• 每个节点的容量：1（Wolf 在每个路口只能封锁一条路）

这正是我们之前网络流模型。

---

完整实现（简化版）

由于完整实现很复杂，这里给出关键部分：

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 2000;  // 估计的节点数

struct Dinic {
    struct Edge {
        int to, cap, flow, rev;
    };
    
    vector<Edge> adj[MAXN];
    int level[MAXN], ptr[MAXN];
    
    void add_edge(int u, int v, int cap) {
        adj[u].push_back({v, cap, 0, (int)adj[v].size()});
        adj[v].push_back({u, 0, 0, (int)adj[u].size() - 1});
    }
    
    bool bfs(int s, int t) {
        memset(level, -1, sizeof(level));
        queue<int> q;
        level[s] = 0;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : adj[u]) {
                if (level[e.to] == -1 && e.flow < e.cap) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }
    
    int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (int& i = ptr[u]; i < adj[u].size(); i++) {
            Edge& e = adj[u][i];
            if (level[e.to] == level[u] + 1 && e.flow < e.cap) {
                int df = dfs(e.to, t, min(f, e.cap - e.flow));
                if (df > 0) {
                    e.flow += df;
                    adj[e.to][e.rev].flow -= df;
                    return df;
                }
            }
        }
        return 0;
    }
    
    int max_flow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            memset(ptr, 0, sizeof(ptr));
            while (int f = dfs(s, t, INF)) {
                flow += f;
            }
        }
        return flow;
    }
    
    void clear() {
        for (int i = 0; i < MAXN; i++) {
            adj[i].clear();
        }
    }
};

struct Point {
    int x, y;
    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

struct Street {
    int x1, y1, x2, y2;
    
    bool is_horizontal() const {
        return y1 == y2;
    }
    
    bool is_vertical() const {
        return x1 == x2;
    }
    
    bool contains(const Point& p) const {
        if (is_horizontal()) {
            return p.y == y1 && min(x1, x2) <= p.x && p.x <= max(x1, x2);
        } else {
            return p.x == x1 && min(y1, y2) <= p.y && p.y <= max(y1, y2);
        }
    }
    
    bool is_edge(const Point& p1, const Point& p2) const {
        return contains(p1) && contains(p2);
    }
};

// 判断两个点之间的边是否是主街道
bool is_main_street(const Point& p1, const Point& p2, 
                   const vector<Street>& streets) {
    for (const auto& s : streets) {
        if (s.is_edge(p1, p2)) {
            return true;
        }
    }
    return false;
}

// 判断点是否在R_D的边界上
bool is_on_boundary(const Point& p, int D) {
    return max(abs(p.x), abs(p.y)) == D;
}

// 判断Wolf是否能阻止BEAR进入R_D
bool can_block(int D, int A, int B, const vector<Street>& streets) {
    // 1. 构建相关点的集合
    set<Point> points;
    
    // 起点
    points.insert(Point(A, B));
    
    // R_D的边界
    for (int x = -D; x <= D; x++) {
        points.insert(Point(x, -D));
        points.insert(Point(x, D));
    }
    for (int y = -D+1; y < D; y++) {
        points.insert(Point(-D, y));
        points.insert(Point(D, y));
    }
    
    // 主街道上的点
    for (const auto& s : streets) {
        if (s.is_horizontal()) {
            for (int x = min(s.x1, s.x2); x <= max(s.x1, s.x2); x++) {
                points.insert(Point(x, s.y1));
            }
        } else {
            for (int y = min(s.y1, s.y2); y <= max(s.y1, s.y2); y++) {
                points.insert(Point(s.x1, y));
            }
        }
    }
    
    // 2. 映射点到ID
    map<Point, int> point_id;
    vector<Point> id_point;
    for (const auto& p : points) {
        point_id[p] = id_point.size();
        id_point.push_back(p);
    }
    
    int n = id_point.size();
    Dinic dinic;
    
    // 3. 构建网络流图
    // 每个点拆分为入点和出点
    int source = 2 * point_id[Point(A, B)] + 1;  // 起点的出点
    int sink = 2 * n;  // 超级汇点
    
    // 节点内部边（容量1）
    for (int i = 0; i < n; i++) {
        int in_node = 2 * i;
        int out_node = 2 * i + 1;
        dinic.add_edge(in_node, out_node, 1);
    }
    
    // 道路边
    for (const auto& p1 : points) {
        int id1 = point_id[p1];
        
        // 四个邻居
        vector<Point> neighbors = {
            Point(p1.x+1, p1.y),
            Point(p1.x-1, p1.y),
            Point(p1.x, p1.y+1),
            Point(p1.x, p1.y-1)
        };
        
        for (const auto& p2 : neighbors) {
            if (points.find(p2) != points.end()) {
                int id2 = point_id[p2];
                
                // 检查是否是主街道
                bool is_main = is_main_street(p1, p2, streets);
                
                int from_node = 2 * id1 + 1;  // p1的出点
                int to_node = 2 * id2;       // p2的入点
                
                int capacity = is_main ? INF : 1;
                dinic.add_edge(from_node, to_node, capacity);
            }
        }
    }
    
    // 连接R_D边界点到汇点
    for (int i = 0; i < n; i++) {
        const Point& p = id_point[i];
        if (is_on_boundary(p, D)) {
            int in_node = 2 * i;  // 入点
            dinic.add_edge(in_node, sink, INF);
        }
    }
    
    // 4. 运行最大流
    int flow = dinic.max_flow(source, sink);
    
    // 5. 判断：如果最大流有限，说明Wolf能阻止
    // 实际上，我们需要检查是否存在从起点到R_D的路径
    // 简化：如果最大流小于某个阈值...
    // 更准确：运行最大流后检查源点能否到达汇点
    
    // 重新运行BFS检查连通性
    dinic.bfs(source, sink);
    return dinic.level[sink] == -1;  // 如果不能到达，说明Wolf能阻止
}

int main() {
    int A, B, N;
    cin >> A >> B >> N;
    
    vector<Street> streets(N);
    for (int i = 0; i < N; i++) {
        cin >> streets[i].x1 >> streets[i].y1 >> streets[i].x2 >> streets[i].y2;
    }
    
    // 二分答案
    int left = 0, right = max(abs(A), abs(B)) + 1;
    int answer = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (can_block(mid, A, B, streets)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

---

算法分析

时间复杂度

• 二分答案：$O(\log(\max(|A|,|B|)))$
• 每次验证 can_block：
  • 收集点：$O(N \cdot L)$，其中 $L$ 是主街道长度
  • 建图：$O(P^2)$，其中 $P$ 是点数
  • Dinic 最大流：$O(E \sqrt{V})$，但这里图比较稀疏
• 总复杂度可接受，因为 $N \le 500$，且坐标范围有限

空间复杂度

• 存储点和边：$O(P + E)$

---

总结

本题的关键在于：

1. 理解游戏规则：Wolf 在每个路口只能封锁一条路，但不能封锁主街道
2. 问题转化：将几何封锁问题转化为图论的最小割问题
3. 网络流建模：使用节点拆点处理每个路口只能封锁一条路的限制
4. 二分答案：寻找最大的 $D$

主要技巧：

• 节点拆点处理节点容量限制
• 主街道设置为无限容量（不能封锁）
• 只考虑相关区域点以减少图规模

这是一道典型的图论与博弈结合的问题，考察了网络流建模能力和对平面图性质的理解。