首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。