首页 > 代码库 > LA 3902 网络
LA 3902 网络
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1903
题意：
n 台计算机，n-1条边成树，有一个服务器，给定一个 k ，要求所有叶子结点，距离服务器的距离 <=k； 所以要在一些地方放服务器；
问最少要放多少个服务器？
图中要在 4 号结点放一个服务器，k = 2;
分析：
1、无根树要转有根树
从下往上覆盖，设4，肯定要比设5要好，5能覆盖到的，4也能覆盖到，所以在用4来覆盖的时候，要从新建树 <(￣︶￣)>
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 1000 + 10; 6 7 int n,s,k; 8 vector<int> gr[maxn],nodes[maxn]; 9 10 11 int fa[maxn];12 void dfs(int u,int f,int d)13 {14 fa[u] = f;15 int nc = gr[u].size();16 if(nc==1&&d>k) nodes[d].push_back(u);17 for(int i=0; i<nc; i++)18 {19 int v = gr[u][i];20 if(v!=f)21 dfs(v,u,d+1);22 }23 }24 25 26 bool covered[maxn];27 28 void dfs2(int u,int f,int d)29 {30 covered[u] = true;31 int nc = gr[u].size();32 for(int i=0; i<nc; i++)33 {34 int v = gr[u][i];35 if(v!=f&&d<k)36 dfs2(v,u,d+1);37 }38 }39 40 int solve()41 {42 int ans = 0;43 memset(covered,0,sizeof(covered));44 for(int d=n-1; d>k; d--)45 {46 for(int i=0; i<nodes[d].size(); i++)47 {48 int u = nodes[d][i];49 if(covered[u])50 continue;51 52 int v = u;53 for(int j=0; j<k; j++)54 v = fa[v];55 dfs2(v,-1,0);56 ans++;57 }58 }59 return ans;60 }61 62 int main()63 {64 int t;65 scanf("%d",&t);66 while(t--)67 {68 scanf("%d%d%d",&n,&s,&k);69 for(int i=1; i<=n; i++)70 {71 gr[i].clear();72 nodes[i].clear();73 }74 75 for(int i=0; i<n-1; i++)76 {77 int a,b;78 scanf("%d%d",&a,&b);79 gr[a].push_back(b);80 gr[b].push_back(a);81 }82 83 dfs(s,-1,0);84 printf("%d\n",solve());85 }86 87 return 0;88 }
LA 3902 网络
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。