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;

}

巴特西

P2016题解

P2016题解

题目描述

题目分析

最新文章

热门文章