【洛谷2279】[HNOI2003] 消防局的设立（贪心）

点此看题面

大致题意： 给你\(N\)个点（其中\(1\)号点为根），并告诉你编号为\(2\sim N\)的点的父亲（\(fa[i]<i\)），现在要在树上选择尽量少的关键点（消防局），使得任意一个点到离它最近的关键点（有可能是它自己）的距离不超过\(2\)，求最少选择的点数。

考虑贪心

很显然，这是一道贪心题。

我们可以将这棵树的节点按照\(BFS\)序依次压入栈中（因为这样可以确保先放入的元素深度小）。每次取出栈顶的元素，若它没有被打过标记它周围距离不超过\(2\)的点中有消防局，就说明要建一个新的消防局。

此时就需要将\(ans\)加\(1\)，按照贪心的思路，应让消防局的深度越小越好，所以给离它祖父距离不超过\(2\)的所有点打上标记即可。

代码

#include<bits/stdc++.h>

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define LL long long

#define N 1000

using namespace std;

int n,m,ee=0,top,ans=0,lnk[N+5],fa[N+5],Stack[N+5],vis[N+5]={0},flag[N+5]={0};

struct edge

{

    int to,nxt;

}e[2*N+5];

inline char tc()

{

    static char ff[100000],*A=ff,*B=ff;

    return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

    x=0;int f=1;char ch;

    while(!isdigit(ch=tc())) if(ch=='-') f=-1;

    while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));

    x*=f;

}

inline void write(LL x)

{

    if(x<0) putchar('-'),x=-x;

    if(x>9) write(x/10);

    putchar(x%10+'0');

}

inline void add(int x,int y)

{

    e[++ee]=(edge){y,lnk[x]},lnk[x]=ee;

}

inline void reset(int x,int dis)//给距离不超过2的点打上标记

{

    if(dis>2) return;//如果距离超过2，就退出

    flag[x]=1;//给这个点标记为距离它不超过2的点中有消防局

    for(register int i=lnk[x];i;i=e[i].nxt) reset(e[i].to,dis+1);//给与当前节点相邻的点进行reset()操作

}

inline void BFS()//一个BFS的过程

{

    register int i,j;

    for(i=1;i<=top;++i)//BFS，将树上的节点按照BFS序压入栈

        for(j=lnk[i];j;j=e[j].nxt)

            if(!vis[e[j].to]) vis[e[j].to]=1,Stack[++top]=e[j].to;

    fa[1]=1;//方便之后的操作，初始化1号节点（根节点）的父亲为自己

    while(top)

    {

        int k=Stack[top--];//取出栈顶的元素

        if(flag[k]) continue;//如果当前节点已经被打过标记，就跳过当前节点

        else ++ans;//否则，说明要新建一个消防局

        reset(fa[fa[k]],0);//对离它祖父距离不超过2的节点打标记

    }

}

int main()

{

    register int i;

    for(read(n),i=2;i<=n;++i) read(fa[i]),add(i,fa[i]),add(fa[i],i);

    vis[Stack[top=1]=1]=1,BFS();//初始化，将1号节点放入栈中

    return write(ans),0;

}

巴特西

【洛谷2279】[HNOI2003] 消防局的设立（贪心）

考虑贪心

代码

最新文章

热门文章