贪婪与动态规划

Question

Xaero 住在一个叫做 Hackland 的国家。 Hackland 具有树状结构，N 个城市由 N−1 条双向道路连接。每个城市的索引都在[1,N]之间，没有两个城市的索引相同。

Hackland总裁认为在城市内出行是安全的。但是，由于哈克兰的照明条件差，在城市 A 到另一个城市 B 之间旅行并不安全。

为了保证人们从一个城市到另一个城市的安全，哈克兰总统决定在国内安装一些灯。每个城市最多可以安装 1 盏灯。甚至有可能一些城市已经安装了灯。根据总统的说法，从一个城市 A 到另一个城市 B 的旅行，如果该路径上至少有 1 个城市安装了灯，则被认为是安全的。

Xaero 知道 Hackland 的预算非常有限。因此，他想帮助他的总统，告诉他最少要安装多少盏灯，这样从一个城市到另一个城市的旅行就变得安全了。

输入格式

输入的第一行包含一个整数T，表示测试用例的数量。每个测试用例的第一行包含一个整数 N，表示称为 Hackland 的国家中的城市数。每个测试用例的下一行包含 N space 个分隔的整数，表示国家的初始配置，即第 i 个位置的“0”表示第 i 个城市没有安装灯，而第 i 个位置的“1”表示有灯已经安装在第i个城市。每个测试用例接下来的 N−1 行包含一对整数 U 和 V，表示城市 U 和城市 V 之间存在双向道路。

我的方法::

对于这个问题，我使用的方法是，我总是选择具有最大度数的节点。照亮它（即使其 deg 为 0，并将其相邻节点的 deg 减少 1），我将继续执行此过程，直到任何节点的 deg 大于零。对于已经变亮的节点，我将它们的 deg 设置为 0，并将其相邻节点的 deg 减少 1。但是我的答案对于某些测试用例不正确??任何人都可以提出我的方法有什么问题吗？？

我在这里分享代码...

#include<bits/stdc++.h>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  

    int T, i, j, max, max_index, index, count, strt, end , N ;        
    bool flag ;

    cin>> T ;        
    while(T--)            
        {            
           cin >> N ;            
           count = 0 ;            
           vector<vector<int>> tree ;            
           vector<int> init(N+1) ;            
           vector<int> deg(N+1) ;            
           fill(deg.begin(),deg.end(),0) ;            
           tree.resize(N+1) ;            
           for(i=1; i<=N; i++)
               cin >> init[i] ;

           for(i=0 ; i < N-1 ; i++)                   
               {                   
               cin>>strt>>end ;                   
               tree[strt].push_back(end) ;                   
               tree[end].push_back(strt) ;                   
               deg[strt] = deg[strt] + 1 ;                   
               deg[end] = deg[end] + 1 ;
              }

           for(i=1; i <=N ; i++)                   
               {                   
                 if(init[i]==1)                         
                     {                         
                         deg[i] = 0 ;                         
                         for(j=0 ; j < tree[i].size(); j++)                                 
                             {                                 
                                index = tree[i][j] ;                                 
                                 deg[index] = deg[index] -1 ;                                 
                             }
                     }                   
             }                                    

       while(1){               
       flag = false ;  //               
       for(i=1 ; i<= N ; i++)               
           {                
              if(deg[i] > 0){
                  flag = true ;                     
                  break ;
              }
         }               
        if(flag==false)
            break ;

        max = deg[1] ;  //            
        max_index =  1;  //            
        for(i=2; i <= N ;i++)
            {                
             if(deg[i] > max)
                {                     
                 max = deg[i] ;                     
                 max_index = i ;
                }                
           }               
        //   cout<<"max_index "<<max_index <<endl ;               
           count = count + 1 ;   // 

          deg[max_index] = 0 ;

          for(j=0; j < tree[max_index].size() ; j++)                  
              {                  
                 index = tree[max_index][j] ;                  
                 deg[index] = deg[index]- 1 ; //                  
              }            
        }

      cout<<count<<endl ;  
    }

    return 0;
}

Answer 1

你的方法是贪心的，而真正的解决方案是基于 DP（顺便说一句，正如你的标题所暗示的）。有很多你可能出错的例子，但这是我认为的一个 - 当多个节点具有相同的度时你应该特别小心并明智地选择：

请注意，即使您为此测试用例输出了正确答案，那也完全是运气问题 - 这里有三个度数为 2 的节点，最好的解决方案是只减轻其中两个 - 2 和 3。根据您给出相等节点的顺序，您最终可能会点亮错误的节点 1。请注意 - 还有许多其他情况下您的解决方案是错误的，这只是我认为最简单的。

贪婪与动态规划

greedy vs dynamic programming

c++

algorithm

greedy