P2279 消防局的设立（贪心+dp）

题目链接：传送门

题目大意：

　　给定一棵树（N个基地N-1条边）；

　　用半径为2的消防局覆盖这N个基地，问最小的消防局数量。

　　（树上距离为k的最小覆盖问题）

思路：

　　每次贪心地找到不被覆盖的最深的一个节点，在它的祖父处放一个消防局。

　　这个消防局所在位置即能将这个节点覆盖到的离它最远的点。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + ;

int N;

vector <int> Edge[MAX_N];

int dep[MAX_N], fa[MAX_N];

bool vis[MAX_N];

int findlower()

{

    int lower = , ind = ;

    for (int i = ; i <= N; i++) {

        if (!vis[i] && dep[i] > lower) {

            lower = dep[i];

            ind = i;

        }

    }

    return ind;

}

void update(int x)

{

    x = fa[fa[x]];

    for (int i = ; i < (int)Edge[x].size(); i++) {

        int y = Edge[x][i];

        vis[y] = true;

        for (int j = ; j < (int)Edge[y].size(); j++) {

            int z = Edge[y][j];

            vis[z] = true;

        }

    }

}

int solve()

{

    memset(vis, false, sizeof vis);

    int ans = ;

    int cur = findlower();

    while (cur) {

        update(cur);

        ans++;

        cur = findlower();

    }

    return ans;

}

void build(int x)//不妨把编号为1的点当作根节点

{

    for (int i = ; i <= N; i++) {

        dep[i] = -;

        fa[i] = i;

    }

    dep[x] = ;

    queue <int> Q;

    Q.push(x);

    while (!Q.empty()) {

        int u = Q.front(); Q.pop();

        for (int i = ; i < (int)Edge[u].size(); i++) {

            int v = Edge[u][i];

            if (dep[v] < ) {

                dep[v] = dep[u] + ;

                fa[v] = u;

                Q.push(v);

            }

        }

    }

}

int main()

{

    cin >> N;

    for (int u = ; u <= N; u++) {

        int v;

        cin >> v;

        Edge[u].push_back(v);

        Edge[v].push_back(u);

    }

    int ans = N;

    build();

    ans = min(ans, solve());

    cout << ans << endl;

    return ;

}

　　前面有点想多了，因为题目中给出的ai < i，所以不需要build直接拿题目中给的树来用就好了。。

　　不过也无伤大雅。

　　然后是膜大佬学到的代码：

　　求树上距离为k的最小覆盖都可以这样做：

　　（时间复杂度为O(N * k)）

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + ;

const int INF = 0x3f3f3f3f;

struct Node{

    int dep, ind;

    Node(int d = , int i = ) : dep(d), ind(i) {}

    bool operator < (const Node& x) const {

        return dep > x.dep;

    }

}nodes[MAX_N];

int fa[MAX_N], dis[MAX_N];

int main()

{

    int N;

    cin >> N;

    nodes[] = Node(, );

    fa[] = ;

    dis[] = INF;

    for (int i = ; i <= N; i++) {

        scanf("%d", fa+i);

        dis[i] = INF;

        nodes[i].ind = i;

        nodes[i].dep = nodes[fa[i]].dep + ;

    }

    sort(nodes+, nodes+N+);

    int ans = ;

    for (int i = ; i <= N; i++) {

        int u = nodes[i].ind;

        int v = fa[u];

        int w = fa[v];

        if (dis[u] >  && dis[v] >  && dis[w] > ) {

            ans++;

            dis[u] = ;

            dis[v] = min(dis[v], );

            dis[w] = min(dis[w], );

            dis[fa[w]] = min(dis[fa[w]], );

            dis[fa[fa[w]]] = min(dis[fa[fa[w]]], );

        }

    }

    cout << ans << endl;

    return ;

}