https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2515

http://7xjob4.com1.z0.glb.clouddn.com/c6a2a6f54f5a6c2cae2c82df2ec552f7

 

题意：给网络图，叶节点是客户端，其他是服务器，设置最少的服务数在服务器上使客户端到服务的距离不超过指定值

思路：将已有的那个服务作根，转换图至有根树，记录各叶子节点的深度；选深度最大的叶节点的 指定值距离 的父亲节点作为设置服务最划算，设置后dfs覆盖状态，只需处理深度大于指定值的叶子节点。

 

1 #include 
      
        2 using namespace std; 3  4 const int maxn=1005; 5 vector 
       
         gr[maxn],nodes[maxn]; 6 int n,s,k,fa[maxn]; 7 bool covered[maxn]; 8  9 void dfs(int u,int f,int d)10 {11     int i,j;12     fa[u]=f;13     int nc=gr[u].size();14     if(nc==1 && d>k)15     {16         nodes[d].push_back(u);17     }18     for(i=0;i
        
         k;d--)47     {48         for(i=0;i