「POI2007 R3」驾驶考试 Driving Exam 题解

在一个有 $n$ 条平行南北道路的网格中，每条道路长 $m$ 米。已有 $p$ 条东西向道路连接相邻的南北道路。我们可以添加最多 $k$ 条东西向道路，目标是最大化能作为起点的南北道路数量。

一个有效的起点要求：从该道路出发，能够到达所有其他南北道路。

核心观察

1. 连通性要求：从起点必须能到达所有其他道路
2. 道路结构：东西向道路连接相邻的南北道路，形成类似梯形的结构
3. 关键限制：只能添加东西向道路，不能添加南北向道路

问题转化

这个问题可以转化为：

• 对于每条南北道路 $i$，计算需要添加多少东西向道路才能让它成为有效起点
• 然后找出在 $k$ 条添加限制下，最多有多少条道路可以成为有效起点

图论建模

将问题建模为有向图：

• 节点：南北道路上的位置（道路编号 + 高度）
• 边：东西向道路（根据方向确定边的方向）

但实际上更高效的做法是：

左右可达性分析

对于一条南北道路 $i$ 能否成为起点，需要满足：

• 从 $i$ 能够向左到达道路 $1$
• 从 $i$ 能够向右到达道路 $n$

这可以分解为两个独立问题。

算法思路

步骤1：预处理左右边界

定义：

• $left[i]$：从道路 $i$ 向左走到道路 $1$ 需要添加的最少道路数
• $right[i]$：从道路 $i$ 向右走到道路 $n$ 需要添加的最少道路数

对于道路 $i$ 成为起点需要的总添加数：

$$need[i] = left[i] + right[i]$$

步骤2：计算左右边界

以计算 $left[i]$ 为例：

从右向左扫描，维护当前能到达的最左位置。对于每个位置 $i$：

• 如果存在从 $i+1$ 到 $i$ 的西向道路，可以直接通过
• 否则需要添加一条道路

更精确的算法：

• 对每个高度，记录东西向道路的存在情况
• 使用动态规划或扫描线计算边界

步骤3：滑动窗口求最大值

现在问题转化为： 在数组 $need[1..n]$ 中，找到长度为 $L$ 的连续子数组，使得其中 $need[i] \leq k$ 的元素最多。

这可以用滑动窗口解决：

• 维护窗口内 $need[i] \leq k$ 的数量
• 滑动窗口求最大值

复杂度分析

• 预处理：$O(n + m + p)$
• 滑动窗口：$O(n)$
• 总复杂度：$O(n + m + p)$，在 $n, m, p \leq 10^5$ 范围内可行

代码框架

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, p, k;
    cin >> n >> m >> p >> k;
    
    vector<vector<pair<int, int>>> east(n), west(n);
    
    // 读入道路数据
    for (int i = 0; i < p; i++) {
        int ni, mi, di;
        cin >> ni >> mi >> di;
        ni--; // 转为0-index
        
        if (di == 0) {
            // 东向道路：从ni到ni+1
            east[ni].push_back({mi, 1});
        } else {
            // 西向道路：从ni+1到ni  
            west[ni].push_back({mi, 1});
        }
    }
    
    // 计算left[i]：从i到1需要添加的道路数
    vector<int> left(n, 0), right(n, 0);
    
    // 实现细节：使用扫描线计算边界
    // 这里省略具体实现...
    
    // 计算总需求
    vector<int> need(n);
    for (int i = 0; i < n; i++) {
        need[i] = left[i] + right[i];
    }
    
    // 滑动窗口找最大值
    int ans = 0, cnt = 0;
    for (int i = 0, j = 0; i < n; i++) {
        while (j < n && (j - i + 1 <= k || need[j] <= k)) {
            if (need[j] <= k) cnt++;
            j++;
        }
        ans = max(ans, cnt);
        if (need[i] <= k) cnt--;
    }
    
    cout << ans << endl;
    return 0;
}

样例分析

输入：

4 3 5 2
2 0 0
2 2 1  
3 3 1
1 1 1
3 3 0

处理过程：

1. 分析现有道路连通性
2. 计算每条道路成为起点需要的添加数
3. 在最多添加2条道路的限制下，找到最多有2条道路可以成为起点

输出：2

总结

本题的关键在于：

1. 将全局连通性分解为左右可达性
2. 预处理每个位置到边界的最小添加数
3. 使用滑动窗口在添加限制下最大化有效起点数

这种"分解+预处理+滑动窗口"的思路在竞赛中很常见，需要熟练掌握。