luoguP2016 战略游戏

题目描述

Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。

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

输入格式

输入文件中数据表示一棵树，描述如下：

第一行 N，表示树中结点的数目。

第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，

接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。

对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。

输出格式

输出文件仅包含一个数，为所求的最少的士兵数目。

分析题目。

如果我们在节点u放一个士兵，那么跟u相连的所有边都会被望到。这是题目中的原话，但我们不应该只拘束于它本身。我们可以进行适当的拓展，然后我们可以进一步得出这样一个结论：当我们在u放了一个士兵以后，与u相连的其他节点就可以被望到，也就是说这些节点可放可不放。而如果我们不在u放士兵，那么其它点就必须放。

设dp(i,0/1)表示以i为根的子树中士兵数量的最小值，0代表i不放士兵，1代表放。由于城堡中的路是一棵树，所以最小值显然具有传递性，具体为从儿子传给父亲。所以我们可以用动态规划来做这题。设u有k个儿子，那么状态转移方程如下：

\[dp[u][0]=\sum_{i=1}^{q}dp[son[i]][1];\\
dp[u][1]=\sum_{i=1}^{q}Min(dp[son[i]][0],dp[son[i]][1]);
\]

初始化dp(x,0)=0,dp(x,1)=1。

显然一遍dfs就可以做完这个过程，时间复杂度为O(N)。

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxn 1501

using namespace std;

struct edge{

    int to,next;

    edge(){}

    edge(const int &_to,const int &_next){

        to=_to,next=_next;

    }

}e[maxn<<1];

int head[maxn],k;

int dp[maxn][2],n;

inline int read(){

    register int x(0),f(1); register char c(getchar());

    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }

    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

inline void add(const int &u,const int &v){ e[k]=edge(v,head[u]); head[u]=k++; }

void dfs(int u,int pre){

    dp[u][0]=0,dp[u][1]=1;

    for(register int i=head[u];~i;i=e[i].next){

        int v=e[i].to;

        if(v==pre) continue;

        dfs(v,u);

        dp[u][0]+=dp[v][1];

        dp[u][1]+=min(dp[v][0],dp[v][1]);

    }

}

int main(){

    memset(head,-1,sizeof head);

    n=read();

    for(register int i=1;i<=n;i++){

        int u=read()+1,cnt=read();

        while(cnt--){ int v=read()+1; add(u,v),add(v,u); }

    }

    memset(dp,0x3f,sizeof dp);

    dfs(1,0);

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

    return 0;

}

巴特西

luoguP2016 战略游戏

题目描述

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

输入格式

输入文件中数据表示一棵树，描述如下：

第一行 N，表示树中结点的数目。

第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，

接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。

对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。

输出格式

输出文件仅包含一个数，为所求的最少的士兵数目。

分析题目。

初始化dp(x,0)=0,dp(x,1)=1。

显然一遍dfs就可以做完这个过程，时间复杂度为O(N)。

最新文章

热门文章