P4186 [USACO18JAN] Cow at Large G题解

问题概述：

在这个问题中，Bessie（牛）会出现在一个特定的谷仓 K，而农民会从一些出口谷仓（每个出口谷仓只有一条隧道）开始追捕 Bessie。目标是计算出为了确保农民能够抓住 Bessie，所需的最小农民数量。农民和 Bessie 会以相同的速度在隧道中移动，农民的最佳策略是通过出口谷仓进行分配，使得他们能够最早地捕捉到 Bessie。

核心思想：

我们要从每个出口谷仓出发，尽可能早地封锁 Bessie 的逃跑路径。
由于图中有 N 个谷仓和 N-1 条隧道，形成一个树结构。每个叶节点（即只有一个连接的谷仓）是一个出口。
我们的目标是计算从某个起点谷仓 K 出发，Bessie 能逃脱的最短时间，并通过计算农民所需的最小数量来确保抓住她。

核心步骤：

树的深度计算：计算从指定的谷仓 K 到其他谷仓的深度，以便了解 Bessie 可能的逃跑路径。
出口谷仓的最短路径：对于每个谷仓，计算到最近的出口谷仓的距离。
DFS 寻找最小农民数量：通过深度优先搜索（DFS），评估每个节点的可捕捉性，递归计算所需的最小农民数量。

代码解释：

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <istream>
#include <limits>
#include <vector>

using ll = int64_t;
using std::cin, std::cout;

const ll maxn = 1e5+5;  // 定义最大节点数
ll n, k, dpts[maxn], rds[maxn], ans;
std::vector<ll> edgs[maxn];  // 用于存储图的邻接表

// 计算每个节点到根节点（谷仓K）的深度
void initdepth(const ll &fth, const ll &now){
    dpts[now] = dpts[fth] + 1;  // 当前节点的深度是父节点的深度 + 1
    for(const ll &nxt: edgs[now]){  // 遍历当前节点的所有邻接节点
        if(nxt == fth) continue;  // 如果邻接节点是父节点，跳过
        initdepth(now, nxt);  // 递归计算邻接节点的深度
    }
}

// 计算每个节点到最近出口谷仓的距离
void initrd(const ll &fth, const ll &now){
    if(edgs[now].size() == 1) rds[now] = 1;  // 叶节点（出口谷仓）到出口的距离是 1
    for(const ll &nxt: edgs[now]){  // 遍历当前节点的所有邻接节点
        if(nxt == fth) continue;  // 跳过父节点
        initrd(now, nxt);  // 递归计算邻接节点的最短距离
        rds[now] = std::min(rds[now], rds[nxt] + 1);  // 更新当前节点到最近出口的距离
    }
}

// DFS 遍历，计算捕获 Bessie 所需的最小农民数量
void dfs(const ll &fth, const ll &now){
    if(rds[now] <= dpts[now]){  // 如果当前节点到最近出口的距离小于等于深度，Bessie 无法逃脱
        ++ans;  // 增加一个农民
        return;
    }
    if(edgs[now].size() == 1){  // 如果是叶节点（出口谷仓）
        ++ans;  // 增加一个农民
        return;
    }
    for(const ll &nxt: edgs[now]){  // 遍历当前节点的所有邻接节点
        if(nxt == fth) continue;  // 跳过父节点
        dfs(now, nxt);  // 递归到子节点
    }
}

int main(){
    std::iostream::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);  // 优化输入输出
    cin >> n >> k;  // 输入节点数 N 和 Bessie 起始位置 K
    std::fill(rds, rds + 1 + n, std::numeric_limits<unsigned int>::max());  // 初始化最近出口距离为最大值
    
    for(ll i = 1; i < n; i++){  // 输入图的边
        ll u, v;
        cin >> u >> v;
        edgs[u].push_back(v);  // u 和 v 之间有隧道
        edgs[v].push_back(u);  // v 和 u 之间有隧道
    }
    
    initdepth(0, k);  // 从根节点计算深度
    initrd(0, k);  // 计算到最近出口的最短距离
    dfs(0, k);  // 从根节点开始 DFS，计算最小农民数量
    cout << ans << '\n';  // 输出最小农民数量
}

代码解释：

初始化：通过邻接表 edgs 存储树的结构。数组 dpts 用于存储每个节点到谷仓 K 的深度，数组 rds 用于存储每个节点到最近出口谷仓的最短距离。
深度计算 initdepth：通过 DFS 从谷仓 K 开始计算每个节点的深度。
出口计算 initrd：通过 DFS 计算每个节点到最近出口谷仓的距离，出口谷仓的距离被初始化为 1（因为出口谷仓只有一个邻接节点）。
DFS 计算最小农民数量 dfs：从根节点开始，通过 DFS 判断每个节点是否需要农民。每当一个节点的到出口的距离大于其深度时，表示这个节点的逃跑路径被封锁，需要一个农民。