贪心：蓝书一道例题的特殊情况

这道题的初始化条件是一个消防站都没有，让你用最小的点去覆盖所有的点。每个点能覆盖的范围是2。

首先，无根树肯定转化为有根树，直接取1为根就好了。

这里有一个贪心的思想：每次我取出那个深度最大的没被覆盖的节点，要去覆盖它，我应该取那个节点？

取它自己会浪费一个半径，只取它爸也挺亏的。

所以直接取它爷爷！

直接取它爷爷作为消防站，然后进行半径为2的覆盖。

如何取出深度最大的点？使用堆就可以了。

全都被覆盖的话就停止，这个是废话了。

我终于会写仿函数辣！

代码：

#include<cstdio>
#include<queue>
const int maxn = 1005;
struct Edges
{
    int next, to;
} e[maxn << 1];
int head[maxn], tot;
int dep[maxn], fa[maxn];
bool vis[maxn];
int n;
struct cmp
{
    bool operator () (const int &a, const int &b) const
    {
        return dep[a] < dep[b];
    }
};
void link(int u, int v)
{
    e[++tot] = (Edges){head[u], v};
    head[u] = tot;
}
void dfs(int u, int f)
{
    dep[u] = dep[f] + 1; fa[u] = f;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if(v == f) continue;
        dfs(v, u);
    }
}
void dfs2(int u, int d)
{
    vis[u] = true;
    if(d == 2) return;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if(v == u) continue;
        dfs2(v, d + 1);
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 2; i <= n; i++)
    {
        int temp; scanf("%d", &temp);
        link(i, temp); link(temp, i);
    }
    dfs(1, 0);
    std::priority_queue<int, std::vector<int>, cmp> heap;
    for(int i = 1; i <= n; i++) heap.push(i);
    int ans = 0;
    while(!heap.empty())
    {
        int x;
        while(!heap.empty() && vis[x = heap.top()]) heap.pop();
        if(heap.empty()) break;
        if(fa[fa[x]]) dfs2(fa[fa[x]], 0);
        else dfs2(1, 0);
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}

P2279 [HNOI2003]消防局的设立

原文：https://www.cnblogs.com/Garen-Wang/p/9882741.html