企业网站特点分析与描述,wordpress描述,用php和mysql做网站,淮安网站网页设计思路#xff1a;删除尽量多的边使得所有点都能在限制距离之内到达一个警局#xff0c;删除边会形成多棵子树#xff0c;最多只能k棵。其实就是以每个警局为根结点#xff0c;把整棵树划分为以警局为根结点的k棵树#xff0c;说明要删除的边的数量就是k-1条#xff0c;即删… 思路删除尽量多的边使得所有点都能在限制距离之内到达一个警局删除边会形成多棵子树最多只能k棵。其实就是以每个警局为根结点把整棵树划分为以警局为根结点的k棵树说明要删除的边的数量就是k-1条即删除的边的条数是一定的。剩下就是为每个节点找根结点考虑从所有警局出发得到到每个点的最短距离则当前节点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 pairint, int
typedef long long LL;
const int maxn 3e5 5;
int vis[maxn], d[maxn];
int n, k, lim;mapPI, intha;
vectorintG[maxn];
queueintq;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)] i1;ha[make_pair(v, u)] i1;G[u].push_back(v);G[v].push_back(u);}memset(vis, 0, sizeof(vis));int cnt 0; //要保留的边的数量 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;
} 如有不当之处欢迎指出 转载于:https://www.cnblogs.com/flyawayl/p/8305313.html
