M_sea

洛谷2279 [HNOI2003]消防局的设立
Luogu算法每次取出没有被覆盖的深度最大的节点,在他的爷爷处放一个消防局。证明自己意会一下即可。用堆维护一下就好...
扫描右侧二维码阅读全文
27
2018/11

洛谷2279 [HNOI2003]消防局的设立

Luogu

算法

每次取出没有被覆盖的深度最大的节点,在他的爷爷处放一个消防局。

证明自己意会一下即可

用堆维护一下就好了。

代码

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

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000+10;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

struct HeapNode {
    int u,dep;
    bool operator <(const HeapNode& rhs) const {
        return dep<rhs.dep;
    }
};

priority_queue<HeapNode> Q;
int dep[MAXN],fa[MAXN];
int n,ans=0;

inline void Dfs(int u) {
    Q.push((HeapNode){u,dep[u]});
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (dep[v]) continue;
        fa[v]=u,dep[v]=dep[u]+1;
        Dfs(v);
    }
}

int vis[MAXN];

inline void tag(int u,int d) {
    vis[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (d<2) tag(v,d+1);
    }
}

int main() {
    n=read();
    for (re int i=2;i<=n;++i) {
        int u=i,v=read();
        addEdge(u,v); addEdge(v,u);
    }
    dep[1]=1; Dfs(1);
    while (!Q.empty()) {
        while (!Q.empty()&&vis[Q.top().u]) Q.pop();
        if (Q.empty()) break;
        HeapNode fr=Q.top(); Q.pop();
        int u=fa[fa[fr.u]];
        if (u) tag(u,0);
        else tag(1,0);
        ++ans;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 12 月 02 日 09 : 21 PM

发表评论

1 条评论

  1. ZCDHJ

    咕咕咕咕