?????????? 思路：刪除盡量多的邊使得所有點都能在限制距離之內(nèi)到達(dá)一個警局，刪除邊會形成多棵子樹，最多只能k棵。其實就是以每個警局為根結(jié)點，把整棵樹劃分為以警局為根結(jié)點的k棵樹，說明要刪除的邊的數(shù)量就是k-1條，即刪除的邊的條數(shù)是一定的。剩下就是為每個節(jié)點找根結(jié)點，考慮從所有警局出發(fā)得到到每個點的最短距離，則當(dāng)前節(jié)點u，一定是從u->v，如果d[v] <= lim則這條邊一定會保留。

AC代碼

#include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 3e5 + 5; int vis[maxn], d[maxn]; int n, k, lim;map<PI, int>ha; vector<int>G[maxn]; queue<int>q;int main() {while(scanf("%d%d%d", &n, &k, &lim) == 3) {ha.clear();while(!q.empty()) q.pop(); for(int i = 1; i <= n; ++i) G[i].clear();memset(d, -1, sizeof(d));int pos;for(int i = 0; i < k; ++i) {scanf("%d", &pos);d[pos] = 0;q.push(pos);}int u, v;for(int i = 0; i < n-1; ++i) {scanf("%d%d", &u, &v);ha[make_pair(u, v)] = i+1;ha[make_pair(v, u)] = i+1;G[u].push_back(v);G[v].push_back(u);}memset(vis, 0, sizeof(vis));int cnt = 0; //要保留的邊的數(shù)量 while(!q.empty()) {int u = q.front(); q.pop();for(int i = 0; i < G[u].size(); ++i) {int v = G[u][i];if(d[v] == -1) {d[v] = d[u] + 1;q.push(v);if(d[v] <= lim) {int id = ha[make_pair(u, v)];vis[id] = 1;++cnt;}}}}printf("%d\n", n-cnt-1);//printf("%d\n", k-1);for(int i = 1; i <= n-1; ++i) {if(!vis[i]) printf("%d ", i);}printf("\n");}return 0; }
如有不當(dāng)之處歡迎指出！

轉(zhuǎn)載于:https://www.cnblogs.com/flyawayl/p/8305313.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 796D Police Stations bfs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。