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][];

int head[M],k,n;

bool vis[M];

struct sa{

    int v,next;

}edg[M*];

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][]=;

    dp[key][]=dp[key][]=;

    int minn=inf;

    for(int i=head[key];i!=-;i=edg[i].next)

    {

        int v=edg[i].v;

        if(vis[v])

        {

            dfs(v);

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

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

            if(dp[v][]<=dp[v][])

            {

                flag=false;

                dp[key][]+=dp[v][];

            }

            else

            {

                dp[key][]+=dp[v][];

                minn=min(minn,dp[v][]-dp[v][]);

            }

        }

    }

        if(flag)

            dp[key][]+=minn;

}

int main()

{

    //freopen("in.txt","r",stdin);

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

    {

        memset(vis,true,sizeof(vis));

        memset(head,-,sizeof(head));

        k=;

        int a,b;

        while(--n)

        {

            scanf("%d%d",&a,&b);

            addedge(a,b);

            addedge(b,a);

        }

        dfs();

        printf("%d\n",min(dp[][],dp[][]));

    }

    return ;

}

巴特西

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

最新文章

热门文章