ACM之路（13）—

　　最近刷了一套（5题）的树型dp题目：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=116767#overview，算是入了个门，做下总结。

　　A题是真正的入门题，只要找出所有的入度为0的点（即每棵树上最高的领导）进行树型dp即可，具体方法同B题，等到了B题再具体讲。

　　C题是给出一棵树，升序输出这棵树上所有满足条件的点，该条件是，去掉该节点以后剩下的所有子树的size不超过原数size的一半。方法是以节点1为头，预处理出所有节点的size，然后用dfs遍历所有的点，找出符合条件的点即可。

　　D题是，给出一个树（树上每个节点都有一个权值）和一个指定的size，找出满足这个size的所有子树中权值最大的一颗子树的权值。因为节点数最大为100，所以只要暴力dp即可。

　　虽然CD两题都不是很难，但还是需要注意一下写法的。

　　重点讲下B和E两题。题意都差不多，给出一棵树，B题是每个点都可以覆盖其相邻的一条边，求覆盖所有边所需最少的点的个数。而E题是，每个点都可以覆盖自己和相邻的节点，求覆盖所有点所需的最少的点的个数。

　　一开始并没有觉得有什么区别，因为都是无环的树，应该B题的方法适用于E，不过最后还是找出了反例。

　　如上图，如果是覆盖所有点，那么只要2，5两个点即可，如果是覆盖边，那么3，4之间的边仍未覆盖，所以有不同，需要采取新的dp方法。

　　对于B题，考虑如果u点不设置点，那么即dp[u][0]=dp[v][1]，即其子节点一定要放一个点（1表示放，0表示不放）；否则，如果u点放置，则dp[u][1]=min(dp[v][0],dp[v][1])。然后用dfs遍历即可。代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 using namespace std;

 const int N = ;

 int dp[N+][];

 vector<int> vec[N+];

 void dfs(int u,int f)

 {

     dp[u][]=;

     dp[u][]=;

     for(int i=;i<vec[u].size();i++)

     {

         int v=vec[u][i];

         if(f==v) continue;

         dfs(v,u);

         dp[u][]+=dp[v][];

         dp[u][]+=min(dp[v][],dp[v][]);

     }

 }

 int main()

 {

     int n;

     while(scanf("%d",&n)==)

     {

         memset(dp,,sizeof(dp));

         for(int i=;i<=N;i++) vec[i].clear();

         for(int i=;i<=n;i++)

         {

             int u,T;

             scanf("%d:(%d)",&u,&T);

             while(T--)

             {

                 int v;

                 scanf("%d",&v);

                 vec[u].push_back(v);

                 vec[v].push_back(u);

             }

         }

         dfs(,-);

         int ans = min(dp[][],dp[][]);

         printf("%d\n",ans);

     }

     return ;

 }

　　对于D题，贪心策略是如果子节点建了，父节点不建；父节点建了，子节点不建。具体的还是见代码理解一下吧：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 using namespace std;

 vector<int> G[+];

 int build[+];

 int ans = ;

 void dfs(int u,int from)

 {

     int f = ; //f=1表示所有子代中具有一个已经放置了点

     for(int i=;i<G[u].size();i++)

     {

         int &v = G[u][i];

         if(v == from) continue;

         dfs(v,u);

         f = f||build[v];

     }

     if(from == -) ans += (f==&&build[u]==);

     else if(build[from] ==  && build[u] ==  && f == )

     {

         ans++;

         build[from] = ; //这是贪心策略的体现，可以手动画图模拟一下

     }

 }

 int main()

 {

     int n;

     while(scanf("%d",&n)==)

     {

         for(int i=;i<=n;i++) G[i].clear();

         memset(build,,sizeof(build));

         for(int i=;i<n;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             G[u].push_back(v);

             G[v].push_back(u);

         }

         ans = ;

         dfs(,-);

         printf("%d\n",ans);

     }

 }

模拟过程大致如下：

由于贪心策略，最后三个节点不涂，倒数第二个涂色，那么3自然不用涂，回溯到2节点的时候，由于1，2，3都没涂，而3是有三个儿子节点可以覆盖它的，故不用管，所以涂1即可，这就是代码中，连续3个没涂的情况下涂最前面那个（也就是from）的缘故。同时这也是和B题不同的一个反例。因为2，3之间的边没被覆盖。

巴特西

ACM之路（13）—— 树型dp

最新文章

热门文章