首页 > 代码库 > CodeForces 796D bfs

CodeForces 796D bfs

CodeForces 796D

题意:n个城市,k个警察局,n-1条边连成树,所有边长都为1,给定的图满足规则:任一城市到离它最近的警察局距离不超过d。 问你最多可以删掉多少条边,使得依旧满足规则。

tags:从所有警察局开始一起bfs,这样当要走向一个点to的时候,肯定是离警察局最近的路。如果to没有走过,就说明这条边 i 是需要的,标记它。最后没有被标记到的边就是不需要的。  注意坑点:d 可以为0

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 300005, M = N<<1;int n, k, d, pli[N], mp[M], ans;bool mark[M], vis[N], vise[M];struct Edge { int to, next; } e[M];int tot, head[N];void Addedge(int u, int v, int x){    e[tot]={v, head[u]}, mp[tot]=x, head[u]=tot++;    e[tot]={u, head[v]}, mp[tot]=x, head[v]=tot++;}queue<int > q;int q1[N], sz;void bfs(){    rep(ca,1,d)    {        sz=0;        while(!q.empty()) { q1[++sz]=q.front(); q.pop(); }        rep(cb,1,sz)        {            int u=q1[cb];            for(int i=head[u]; i!=-1; i=e[i].next)                if(vise[mp[i]]==false)            {                vise[mp[i]]=true;                int to=e[i].to;                if(vis[to]==false) {                    q.push(to), vis[to]=true, mark[mp[i]]=true;                }            }        }    }}void Init(){    tot=0;  ans=0;    mes(head, -1);    mes(mark, false);    mes(vis, false);    mes(vise, false);}int main(){    scanf("%d %d %d", &n, &k, &d);    Init();    rep(i,1,k)    {        scanf("%d", &pli[i]);        vis[pli[i]]=true, q.push(pli[i]);    }    int u, v;    rep(i,1,n-1)    {        scanf("%d %d", &u, &v);        Addedge(u, v, i);    }    if(d==0)    {        printf("%d\n", n-1);        rep(i,1,n-1) printf("%d ", i);        return 0;    }    bfs();    rep(i,1,n-1) if(mark[i]==false) ++ans;    printf("%d\n", ans);    rep(i,1,n-1) if(mark[i]==false) printf("%d ", i);    return 0;}

CodeForces 796D bfs