POJ 3659 Cell Phone Network 最小支配集模板题（树形dp）

题意：有以个有 N 个节点的树形地图，问在这些顶点上最少建多少个电话杆，可以使得所有顶点被覆盖到，一个节点如果建立了电话杆，那么和它直接相连的顶点也会被覆盖到。

分析：用最少的点覆盖所有的点，即为求最少支配集。可以用树形DP。

       ① dp[r][0] += min(dp[i][0],dp[i][1],dp[i][2])    dp[r][0]表示在自 r 顶点自身建，以 r 为根节点的树所需要的最少覆盖数。
       ② dp[r][1] += min(dp[i][0],dp[i][1])                dp[r][1]表示在r 的子节点建，     以 r 为根节点的树所需要的最少覆盖数。
       ③ dp[r][2] += min(dp[i][0],dp[i][1])                dp[r][2]表示在r 的父节点建，     以 r 为根节点的数所需要的最少覆盖数。

对于dp[i][1],要考虑全面，也就是说：必须要有一个孩子建塔，才能保证i被覆盖（Min=sum(min(dp[v][0]-dp[i][1]))，也就是当所有孩子的dp[v][0]>dp[v][i]时，Min表示他们差值最小的那个差值）。

所以方程是dp[i][1]+=min(dp[v][0],dp[1])（至少存在一个孩子的dp[v][0]<=dp[v][1]，否则要dp[i][1]+=Min）；

AC代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define M 10007
#define inf 0x3f3f3f
using namespace std;
int dp[M][3];
int head[M],k,n;
bool vis[M];

struct sa{
    int v,next;
}edg[M*2];

void addedge(int u,int v)
{
    edg[k].v=v;
    edg[k].next=head[u];
    head[u]=k++;
}

void dfs(int key)
{
    bool flag=true;
    vis[key]=false;
    dp[key][0]=1;
    dp[key][1]=dp[key][2]=0;
    int minn=inf;
    for(int i=head[key];i!=-1;i=edg[i].next)
    {
        int v=edg[i].v;
        if(vis[v])
        {
            dfs(v);
            dp[key][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
            dp[key][2]+=min(dp[v][0],dp[v][1]);
            if(dp[v][0]<=dp[v][1])
            {
                flag=false;
                dp[key][1]+=dp[v][0];
            }
            else
            {
                dp[key][1]+=dp[v][1];
                minn=min(minn,dp[v][0]-dp[v][1]);
            }
        }
    }
        if(flag)
            dp[key][1]+=minn;
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        memset(vis,true,sizeof(vis));
        memset(head,-1,sizeof(head));
        k=1;
        int a,b;
        while(--n)
        {
            scanf("%d%d",&a,&b);
            addedge(a,b);
            addedge(b,a);
        }
        dfs(1);
        printf("%d
",min(dp[1][0],dp[1][1]));
    }
    return 0;
}

View Code