poj 3659 树形dp（树上的最小支配集）

56 阅读 0 评论 37 点赞

我是靠谱客的博主繁荣板凳，最近开发中收集的这篇文章主要介绍poj 3659 树形dp（树上的最小支配集），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：求树的最小支配集。

思路：动态规划。一开始每个点只取了两个变量，表示在以其为根的子树中选择和不选择该点的最少点数。由一组数据（6个点的路径）发现了问题，考虑第3个点的时候，如果不选择此点，那么第4个点必须要选取，实际上这是不必的。该组数据的最优解是选择第2和第5个点。

那么每个点加上一个变量好了：

dp1[x]表示选择第x个点。

dp0[x][0]表示不选择第x个点，而且该点并没有被儿子所覆盖。

dp0[x][1]表示不选择第x个点，但是该点已经被儿子所覆盖了，即至少有一个儿子被选择。

如此一来就对了，转移方程见代码，懒得写了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
using namespace std;
#define clc(s,t) memset(s,t,sizeof(s))
#define INF 0x3fffffff
#define N 10005
struct edge{
    int y,next;
}e[N<<1];
int first[N],n,top;
int dp1[N],dp0[N][2];
void add(int x,int y){
    e[top].y = y;
    e[top].next = first[x];
    first[x] = top++;
}
void dfs(int x,int fa){
    int son = 1,tmp = 0;
    for(int i = first[x];i!=-1;i=e[i].next){
        if(e[i].y != fa){
            son = 0;
            dfs(e[i].y,x);
            if(!dp0[x][1])//考虑第一个儿子
                dp0[x][1] = dp1[e[i].y];
            else
                dp0[x][1] = min(tmp+dp1[e[i].y] , dp0[x][1]+min(dp0[e[i].y][1],dp1[e[i].y]));
            tmp +=min(dp0[e[i].y][1],dp1[e[i].y]);
            dp1[x] += min(min(dp0[e[i].y][0],dp0[e[i].y][1]),dp1[e[i].y]);
            dp0[x][0] += dp0[e[i].y][1];
        }
    }
    dp1[x] ++;
    if(son)
        dp0[x][1] = 1;
}
int main(){
    int i,a,b;
    clc(first,-1);
    clc(dp1, 0);
    clc(dp0, 0);
    top = 0;
    scanf("%d",&n);
    for(i = 1;i<n;i++){
        scanf("%d %d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    printf("%dn",min(dp1[1],dp0[1][1]));
    return 0;
}