uva 1267-白红宇

uva 1267

阅读量：5167 次

发布时间：2019-06-13

本文共 2959 字，大约阅读时间需要 9 分钟。

分类：贪心，树结构

题意： n个结点，以最小生成树方式连接，有一个结点是服务器，可以服务k以内的叶子结点，求还需要放几个服务器，覆盖所有叶子结点

输入：数据组数T，结点数n，距离k， n-1行表示连接关系

输出：还需要放置的最小服务器数

解法：

第一步，构建有根树，获得结点的深度值和叶子结点

从最底层的叶子结点，自底向上贪心解决覆盖问题

注意，没加入一个服务器，dfs距离k以内的所有结点探测是否要覆盖叶子结点，但不是只遍历一次，注意算法的思路

注意是否需要考虑边界条件和特殊情况

#include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         using namespace std;///宏定义const int INF = 990000000;const int MAXN = 1015;const int maxn = MAXN;///全局变量 和 函数int s, k, n;struct node{ int lable; int height; int parent; bool isLeave, isCoverd, isServer; vector
                         
                           children; bool operator < (const node& T) const { return height < T.height; }};node tree[maxn];priority_queue
                          
                            que;int cntAns = 0;bool vis[maxn], vis2[maxn];void buildTree(int r, int h){ vis[r] = true; tree[r].height = h; if (tree[r].isLeave && !tree[r].isServer) //如果叶子结点是服务器，但根结点情况除外 return; int nums = tree[r].children.size(); for (int i = 0; i < nums; i++) { int cur = tree[r].children[i]; if (vis[cur]) continue; tree[cur].parent = r; buildTree(cur, h + 1); }}void cover(int cur, int dep){ if (dep > k) return;// vis2[cur] = true; //不是遍历一次 WA的原因 if (tree[cur].isLeave) { tree[cur].isCoverd = true; return; } int nums = tree[cur].children.size(); int nextNum; for (int i = 0; i < nums; i++) { nextNum = tree[cur].children[i];// if (!vis2[nextNum]) cover(nextNum, dep + 1); } }void solve(){ while (!que.empty()) { node curNode = que.top(); int cur = curNode.lable; if (tree[cur].isCoverd) { que.pop(); continue; } que.pop(); int fa = cur; bool putit = true; for (int i = 0; i < k; i++) { fa = tree[fa].parent; //如果已经有服务器，则覆盖本结点 if (fa != 0 && tree[fa].isServer) { putit = false; break; } if (fa == 0) break; } if (putit) { tree[cur].isCoverd = true; cntAns++; tree[fa].isServer = true; cover(fa, 0); } if (!putit) tree[cur].isCoverd = true; }}int main(){ ///变量定义 int T; scanf("%d", &T); while (T--) { //清空结构 memset(vis, false, sizeof(vis)); memset(vis2, false, sizeof(vis2)); //不需要vis2数组 for (int i = 0; i < maxn; i++) { tree[i].lable = i; tree[i].parent = tree[i].height = 0; tree[i].isCoverd = tree[i].isLeave = tree[i].isServer = false; tree[i].children.clear(); } while (!que.empty()) que.pop(); cntAns = 0; scanf("%d", &n); scanf("%d%d", &s, &k); for (int i = 0; i < n - 1; i++) { int from, to; scanf("%d%d", &from, &to); tree[from].children.push_back(to); tree[to].children.push_back(from); } tree[s].isServer = true; tree[s].isCoverd = true; //服务器结点要加入coverd for (int i = 1; i <= n; i++) { if(tree[i].children.size() == 1) tree[i].isLeave = true; } int root = s; //建有根树 buildTree(root, 1); for (int i = 1; i <= n; i++) { if(tree[i].isLeave && !tree[i].isCoverd) //没有覆盖的叶子加入 que.push(tree[i]); } //进行放置统计 solve(); printf("%d\n", cntAns); } ///结束 return 0;}

转载于:https://www.cnblogs.com/rayforsure/p/3335723.html

你可能感兴趣的文章