CF796D Police Stations BFS+染色

题意：给定一棵树，树上有一些点是警察局，要求所有点到最近的警察局的距离不大于 $d$，求最多能删几条边 ?

题解：

考虑什么时候一条边可以被断开：这条边的两个端点被两个不同的警察局覆盖掉.

我们要设计一种染色方案，使得整棵树都被覆盖，且每个警察局覆盖的范围尽量小.

那么，我们可以使用 $BFS$ 算法，拓展到不超过 $d$ 的距离，然后染色就.

最后看一下哪些边的端点颜色不同即可.

#include <bits/stdc++.h>

#define N 300006

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

vector<int>G;

queue<int>q;

int n,k,d,edges,vis[N],hd[N],to[N<<1],nex[N<<1],U[N],V[N],dis[N];

void add(int u,int v)

{

    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;

}

int main()

{

    int i,j;

    // setIO("input");

    scanf("%d%d%d",&n,&k,&d);

    for(i=1;i<=k;++i)

    {

        int x;

        scanf("%d",&x);

        vis[x]=x,q.push(x);

    }

    for(i=1;i<n;++i)

    {

        int u,v;

        scanf("%d%d",&u,&v), add(u,v),add(v,u);

        U[i]=u, V[i]=v;

    }

    for(;!q.empty();)

    {

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

        for(int i=hd[u];i;i=nex[i])

        {

            int v=to[i];

            if(!vis[v] && dis[u]+1<=d)

            {

                vis[v]=vis[u];

                dis[v]=dis[u]+1;

                q.push(v);

            }

        }

    }

    for(i=1;i<n;++i)

    {

        if(vis[U[i]]!=vis[V[i]])

        {

            G.push_back(i);

        }

    }

    printf("%d\n",G.size());

    for(i=0;i<G.size();++i) printf("%d ",G[i]);

    return 0;

}

巴特西

CF796D Police Stations BFS+染色

最新文章

热门文章