P2016题解

题目描述

Bob要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。

注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。

请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。

题目分析

题目需要求解最少士兵数量，数据规模不大，可以使用树上dp求解。

考虑 \(dp\) 数组表示的意义：由于每个点都可以放或者不放，而这两种情况又会对周围的点产生不同的影响

我们用 \(dp_{i,j} (j \in [0,1])\) 来表示第 \(i\) 个点放置/不放置时所需要的最小花费。

如何满足无后效性的要求？使用 \(dfs\)，从深度大的节点向深度小的节点转移即可。

考虑转移方程:

• 若点 \(i\) 不放置，则与 \(i\) 相连的所有节点都需要放置士兵。转移方程为 \(dp_{i,0} = \sum dp_{to,1}\)。
• 若点 \(i\) 放置，则与 \(i\) 相连的点可以选择放置会不放置。转移方程为 $dp_{i,1} = \sum \min{dp_{to,0},dp_{to,1}}。

题目代码如下：

//author : yuhang-ren
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 1511
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x>9)
    {
        write_(x/10);
    }
    putchar(x%10+'0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
struct node
{
    int to,nxt;
}edge[2*max_n];
int n,dp[max_n][2],head[max_n],tot;
void add(int u,int v)
{
    edge[++tot].to = v;
    edge[tot].nxt = head[u];
    head[u] = tot;
}
int ans = 0;
void dfs(int u,int fa)
{
    dp[u][0] = 0; 
    dp[u][1] = 1;
    for(int i = head[u];i;i = edge[i].nxt)
    {
        int v = edge[i].to;
        if(v == fa)
        {
            continue;
        }
        dfs(v,u);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0],dp[v][1]);
    }
}
signed main()
{
    #if _clang_
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif 
    read(n);
    int u,num,v;
    for(int i = 1;i<=n;i++)
    {
        read(u),read(num);
        for(int j = 1;j<=num;j++)
        {
            read(v);
            add(u,v);
            add(v,u);
        }
    }
    dfs(0,-1);
    writeln(min(dp[0][0],dp[0][1]));
    return 0;
}