题解 P4186 [USACO18JAN]Cow at Large G

· · 题解

Part 0：前言

这是本蒟蒻的第一篇题解，求赞 & 求管理员大大通过 \text{QAQ}

Part 1：读题

题目要求：Bessie 在一棵根为 K 号节点的树根上，要求在叶子节点上放置农民并最小化农民数量（农民可移动），使和农民速度相同的 Bessie 在不接触到农民的前提下无法走到任意一个叶子节点。真简洁

Part 2：初步理清思路

思路一：硬怼！

就像 大佬 @bessie_goes_moo 的思路 那样，直接模拟题意。

预计时间复杂度：\text{O}(ans \times n)

最大时间复杂度：\text{O}(n^2)

好像能被卡掉（雾

思路二：正解

就是给每一个叶子节点放一个农民，让他们和 Bessie 一起走，看看 Bessie 能遇到几个人。

这里借用一下 @llzzxx712 大佬的图 （我懒得画）：

我们先给每个叶子节点安排一个农民：

（橙点为农民）

然后让农民一直往上走，直到遇到 会影分身的 Bessie，这里就是他们能控制的点：

（红点为农民可控制的点）

然后开始 dfs，让 Bessie 开始走。Bessie 遇到了两个红点，说明只需要两个农民就可以锁住 Bessie 了（在节点 9 \ (10) 和节点 17 ）。

同理，我们也可以模拟一下样例。鉴于篇幅有限，我放在了 云剪贴板 里面，大家可自行观看。

Part 3：深入思考，获得代码思路

大概思路一有，代码的思路也就出来了：在每一个被农民控制的点做一个标记，再遍历整棵树，遇到标记就 \text{ans} 加一。最后输出 \text{ans} 即可。

Part 4：代码

这里我提供 3 种不同的标记实现方式：

  1. 在第一遍遍历的时候记录下每个结点的父亲节点，再单独从每个叶子节点向上反，做标记。

  2. 在第一遍遍历的时候用一个栈记录路径，每次找到叶子节点就在 (栈顶的位置 \times \ \dfrac{1}{2} ) 处的节点做标记。

  3. 在第一遍遍历的时候记录一个 \text{down} 数组表示离这里最近的叶子节点的距离。在第二遍遍历的时候，如果当前的深度 \ge 当前节点的 \text{down} 值，就算遇到了标记。

方式 1 的代码：

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

int n, k, a, b, l, fa[100001], dep[100001] = {-1}, ans;
bool leaf[100001], flag[100001];
vector<int> tree[100001];

void dfs1 (int i, int fr)
{
    leaf[i] = 1;
    fa[i] = fr;
    dep[i] = dep[fr] + 1;
    for (int k = 0; k < tree[i].size(); k++)
    {
        int now = tree[i][k];
        if (now != fr)
        {
            leaf[i] = 0;
            dfs1 (now, i);
        }
    }
}

void dfs2 (int i, int fr)
{
    if (flag[i])
    {
        ans++;
        return;
    }
    for (int k = 0; k < tree[i].size(); k++)
    {
        int now = tree[i][k];
        if (now != fr)
            dfs2 (now, i);
    }
}

int main()
{
    cin >> n >> k;
    fa[k] = 0;
    for (int i = 1; i < n; i++)
    {
        cin >> a >> b;
        tree[a].push_back (b);
        tree[b].push_back (a);
    }
    dfs1 (k, 0);
    for (int i = 1; i <= n; i++)
    {
        if (leaf[i])
        {
            int dis = i;
            for (int j = 1; j <= dep[i] / 2; j++)
                dis = fa[dis];
            flag[dis] = 1;
        }
    }
    dfs2 (k, 0);
    cout << ans;
    return 0;
}

提交记录

方式 2 的代码：

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

int n, k, a, b, l, st[100001], top, fa[100001], dep[100001] = {-1}, ans;
bool leaf[100001], flag[100001];
vector<int> tree[100001];

void dfs1 (int i, int fr)
{
    st[++top] = i;
    if (tree[i].size() == 1)
    {
        flag[st[top / 2 + 1]] = 1;
        top--;
        return;
    }
    for (int k = 0; k < tree[i].size(); k++)
    {
        int now = tree[i][k];
        if (now != fr)
            dfs1 (now, i);
    }
    top--;
}

void dfs2 (int i, int fr)
{
    if (flag[i])
    {
        ans++;
        return;
    }
    for (int k = 0; k < tree[i].size(); k++)
    {
        int now = tree[i][k];
        if (now != fr)
            dfs2 (now, i);
    }
}

int main()
{
    cin >> n >> k;
    fa[k] = 0;
    for (int i = 1; i < n; i++)
    {
        cin >> a >> b;
        tree[a].push_back (b);
        tree[b].push_back (a);
    }
    dfs1 (k, 0);
    dfs2 (k, 0);
    cout << ans;
    return 0;
}

提交记录

方案 3 的代码：

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

int n, k, a, b, down[100001], ans;
vector<int> tree[100001];

void dfs1 (int i, int fr)
{
    down[i] = 0x7fffffff;
    if (tree[i].size() == 1)
        down[i] = 0;

    for (int k = 0; k < tree[i].size(); k++)
    {
        int now = tree[i][k];
        if (now != fr)
        {
            dfs1 (now, i);
            down[i] = min (down[now] + 1, down[i]);
        }
    }
}

void dfs2 (int i, int fr, int deep)
{
    if (deep >= down[i])
    {
        ans++;
        return;
    }
    for (int k = 0; k < tree[i].size(); k++)
    {
        int now = tree[i][k];
        if (now != fr)
            dfs2 (now, i, deep + 1);
    }
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        cin >> a >> b;
        tree[a].push_back (b);
        tree[b].push_back (a);
    }
    dfs1 (k, 0);
    dfs2 (k, 0, 0);
    cout << ans;
    return 0;
}

提交记录

完结撒花~~~