题目大意

    N个节点构成一棵树形结构，在其中若干个节点上放置士兵，与被放置士兵的节点相连的边会被士兵看守。问需要至少在多少个节点上放置士兵，才能使得N-1条边都被看守。

题目分析

    题目描述的结构为树形，且最优化问题，可以考虑使用树形动态规划来解决。将结构按照树根在上，树叶在下的结构进行排列，为了保证无后效性，需要对i节点上有无士兵的情况单独处理，设置状态 dp[i][0] 表示在节点i不放置士兵的情况下，节点i以下的边都被看守所需要放置士兵的最少数目；dp[i][1]表示在节点i放置士兵的情况下，节点i以下的所有边都被看守所需要放置士兵的最少数目。显然有递推关系： 

dp[i][0] = sum{dp[son_of_i][1]} 

dp[i][1] = sum{min{dp[son_of_i][0], dp[son_of_i][1]}}

实现(c++)

#include
     
      #include
      
       #include
       
        #define min(a, b) a < b? a:busing namespace std;vector
        
          gGraph[1505]; //使用 vector
         
           gGraph[1505]， 而不使用 vector
          
           
             > //是因为题目多组数据，若使用 vector
            
             
               >，则在每组数据都会进行对 外层vecotr的 resize操作，减低效率int dp[1505][2];void Travel(int node){ if (gGraph[node].empty()){ dp[node][0] = 0; //node节点不放置士兵的情况下，node节点以下的所有边都被看守所需要的士兵总数 dp[node][1] = 1; //node节点放置士兵的情况下，node节点以下的所有边都被看守所需要的士兵总数 return; } dp[node][1] = 1; for (int i = 0; i < gGraph[node].size(); i++){ Travel(gGraph[node][i]); //由叶子到根进行递推，后序遍历 //node节点不放置士兵的情况下，需要node节点的子节点都放置士兵 dp[node][0] += dp[gGraph[node][i]][1]; //node节点放置士兵，则其子节点可放可不放，选取最小值即可 dp[node][1] += min(dp[gGraph[node][i]][1], dp[gGraph[node][i]][0]); }}int main(){ int n, root; while (scanf("%d", &n) != EOF){ for (int i = 0; i < n; i++){ gGraph[i].clear(); } int node, num_adjacent, node_adjacent; root = -1; memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++){ scanf("%d:(%d)", &node, &num_adjacent); if (root < 0) root = node; for (int j = 0; j < num_adjacent; j++){ scanf("%d", &node_adjacent); gGraph[node].push_back(node_adjacent); } } Travel(root); int result = min(dp[root][0], dp[root][1]); printf("%d\n", result); } return 0;}