题解 | CellPhone-牛客假日团队赛8A题

题目描述

Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his $N (1 ≤ N ≤ 10,000)$ pastures (conveniently numbered 1..N) so they can all communicate.
Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B $(1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B)$ there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.
Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

输入描述:

* Line 1: A single integer: N
* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

输出描述:

* Line 1: A single integer indicating the minimum number of towers to install

示例1

输入

5
1 3
5 2
4 3
3 5

输出

2

说明

The towers can be placed at pastures 2 and 3 or pastures 3 and 5.

解答

题意：农夫给他的每个牛发另一个手机（有点扯），现在要在农场建设信号塔以便所有的牛可以相互联系，每个信号塔可以供和他相连的农场使用，所有农场形成一颗树，问要达到要求最少建塔的数量。也就是给一颗树，每个节点可以覆盖和他相连的所有节点，现在问你用最少的点把所有的点覆盖完。
这个题目和poj1463有点相似，poj1463是用点覆盖边，相对简单很多（poj1463解题报告）；
解题：可以用动态规划，也可以用最小支配集。
一、现在先说用动态规划的思路：
根据题意知道每个节点有三种状态：
1、点 $i$ 建塔，i的所有孩子都覆盖，用 $dp[i][0]$ 表示；
2、点 $i$ 不建塔， $i$ 和 $i$ 的所有孩子都覆盖，用 $dp[i][1]$ 表示；
3、点 $i$ 不建塔， $i$ 不覆盖， $i$ 的所有孩子都覆盖，用 $dp[i][2]$ 表示；
如果这样不好理解那么这样理解可能容易一点（参考别人的）：覆盖 $i$ ，要么是父节点覆盖，要么是自己，要么是孩子，所以三种状态（和上面的对应）：
1、点 $i$ 自己覆盖自己， $i$ 的所有孩子都覆盖，用 $dp[i][0]$ 表示；
2、点 $i$ 被自己的孩子覆盖， $i$ 和 $i$ 的所有孩子都覆盖，用 $dp[i][1]$ 表示；
3、点 $i$ 被父节点覆盖， $i$ 的所有孩子都覆盖，用 $dp[i][2]$ 表示；
那么动态转移方程就是（ $v$ 是 $i$ 的孩子）：
$dp[i][0]+=min(dp[v][0],dp[v][1],dp[v][2]);$
$dp[i][2]+=min(dp[v][0],dp[v][1]);$
对于 $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]\leq dp[v][1]$ ，否则要 $dp[i][1]+=Min$ ）；

#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\n",min(dp[1][0],dp[1][1]));
    }
    return 0;
}

来源：ACBoy_lhc