OJ：https://vjudge.net/problem/UVALive-3902
题目大意：给你一棵树，但是这个树是没有指明根节点的，也就是一个没有回路的图。图上有很多的节点，客户端在叶子节点上，有一个服务器位于s位置，一个服务器的覆盖范围最多是k个距离，大于k的就不能进行覆盖了，现在的需求是覆盖到所有的客户端，问最少还要加几个服务器。
感觉是一个很有意思的题，但是题面的描述并不清楚，没有直接说明客户端节点只能存在于树的叶子节点上，而是以一个样例进行说明的，这个对我造成了一定的影响，我以为除了s节点之外的所有节点都是属于叶子客户端节点，也就是说，我们要用服务器节点去覆盖全部的节点。这就导致一直提交不过，后来看了别人的代码才发现这个问题，哎！！！
解题的思想就是，首先将给定的图转换为一个树的形式，且因为图中存在一个非常天然的根，所以直接以当前节点作树的根节点。
然后找到这棵树中没有被覆盖的客户端的最深的节点（深，就是在树中的深度，这就利用了树的特性，树有深度的概念，而图没有），再找到一个刚好能覆盖到这个最深的节点的且离那个节点最远的位置，在当前位置放置一个服务器，然后利用当前服务器去覆盖一些客户端。然后循环这个过程，最终就解决了这个问题。我们要保证每一个客户端被覆盖，那么根据贪心的思想，在能覆盖当前节点的同时，要尽量去覆盖到更多其他的节点，要如何覆盖到更多的节点？就是要离当前节点远一点了，越远就越可能覆盖到更多的节点。那为什么要找最深的节点，这就是贪心策略了，首先要保证每一个节点被覆盖，也就是说，最深的节点也需要被覆盖，那么是不是就是回到之前的那去了。
#include<stdlib.h> #include<stdio.h> #include<string.h> #define max(x,y) x > y ? x : y #define MAX 1005 typedef struct{ // 当前深度的叶子节点的个数 int size; // 保存叶子节点 int index[MAX]; }Deep; // 保存节点在树上的父节点 int father[MAX]; // 保存图 int map[MAX][MAX]; // 保存某一深度的叶子节点 Deep deeps[MAX]; // 标识当前客户端是否有能提供服务的服务器 int vis[MAX]; int t,n,s,k; void dfs1(int cur,int pre,int c){ vis[cur] = 1; if(c == 0){ return ; } for(int i=1;i<=n;i++){ if(map[cur][i] && i!=pre){ dfs1(i,cur,c-1); } } } // 树转图 int dfs(int cur,int pre,int deep){ father[cur] = pre; int d = 0; // 判断当前字符是否是一个叶子节点 // 题面中没有明说客户端节点必须要在叶子节点上，而是以一个样例的方式来进行说明的 int count = 0; for(int i=1;i<=n;i++){ if(map[cur][i] ){ count++; if(i != pre){ int r = dfs(i,cur,deep+1); d = max(d,r); } } } // 如果等于1的话，说明当前节点是一个叶子节点 if(count == 1){ deeps[deep].index[deeps[deep].size++] = cur; } return d + 1; } int solve(int maxDeep){ int curDeep = maxDeep; int res = 0; for(;curDeep>k+1;curDeep--){ int size = deeps[curDeep].size; for(int j=0;j<size;j++){ if(!vis[deeps[curDeep].index[j]]){ int curNode = deeps[curDeep].index[j]; for(int i=0;i<k;i++){ curNode = father[curNode]; } res++; dfs1(curNode,0,k); } } } return res; } void initDeep(int n){ for(int i=1;i<=n;i++){ deeps[i].size = 0; } } int main(){ scanf("%d",&t); for(;t>0;t--){ scanf("%d%d%d",&n,&s,&k); memset(vis,0,sizeof(vis)); memset(map,0,sizeof(map)); initDeep(n); for(int j=0;j<n-1;j++){ int x,y; scanf("%d%d",&x,&y); map[x][y] = 1; map[y][x] = 1; } int maxDeep = dfs(s,0,1); printf("%d\n",solve(maxDeep)); } }
还有就是我之前遇到的问题，我之前以为要覆盖所有的节点，而不是只覆盖所有的子节点，所以出现了问题，其实啊这是跟树的结构有关，按照我之前的代码逻辑，如果树的结构是下面这个样子的，就能过
但是如果是下面这种结构就会出错
看出区别了吗？如果k等于1的话，下面这个图按照我之前的想法，需要新增3个服务器，但是按照题目的意思，其实只需要新增两个。
