【题解】保安站岗[P2458]皇宫看守[LOJ10157][SDOI2006]

【题解】保安站岗[P2458]皇宫看守[LOJ10157][SDOI2006]

传送门:皇宫看守([LOJ10157]) 保安站岗 ([P2458]) ([SDOI2006])

【题目描述】

给你一棵树,要求树上每个点都要有人看守,在不同的点安排守卫所需 (Monney) 不同。
守卫站在某个端点上时,他除了能看守住他所站的那个点,也能看守通过一条边与之相连的另一个端点,因此一个守卫可能同时能看守住多个点,因此没有必要在每个端点上都安排守卫。

要求在能够看守住所有点的前提下,使得花费的 (Monney) 最少。

【输入】

(1) 行一个整数 (n),表示树中节点的数目。
接下来 (n) 行,每行描述每个结点的信息,依次为:该结点标号 (i),在该结点安置保安所需的经费 (k_i),该边的儿子数 (m),接下来 (m) 个数,分别是这个节点的 (m) 个儿子的标号 (r_1,r_2,r_3...r_m)

对于一个 (n) 个结点的树,其结点标号在 (1)(n) 之间,且标号不重复。

【输出】

输出一行一个整数,表示花费的最少 (Monney)

【样例】

样例输入:
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

样例输出:
25

【数据范围】

(100\%) (1 leqslant N leqslant 1500,1 leqslant k_i leqslant 10000)


【分析】

一道经典的树形 (dp)

(dp[i][0]) 表示:自己不是守卫,父亲不是守卫,儿子是守卫

(dp[i][1]) 表示:自己是守卫,父亲不知道,儿子不知道

(dp[i][2]) 表示:自己不是守卫,父亲是守卫,儿子不知道

在树上 (dfs) 遍历。

每到达一个 (x),先对其进行初始化:(dp[x][1]=w[x],dp[x][2]=dp[x][0]=0)(其中 (w[x]) 为在 (x) 这个位置放守卫所需 (Monney))。

然后遍历它的若干个儿子结点,更新三个 (dp[x][?])

((1).) (dp[x][1])(x) 是守卫,(x) 的父亲不知道,(x) 的儿子 (to) 不知道
对于 (to) 来说,(to) 的父亲一定是守卫,所以 (dp[to][0]) 就不统计了,于是有:(dp[x][1]=sum_{to in son[x]} min(dp[to][1],dp[to][2]))

((2).) (dp[x][2])(x) 不是守卫,(x) 的父亲是守卫,(x) 的儿子 (to) 不知道

对于 (to) 来说,(to) 的父亲不可能是守卫,于是有:(dp[x][2]=sum_{to in son[x]} min(dp[to][1],dp[to][0]))

((3).) (dp[x][0])(x) 不是守卫,(x) 的父亲不是守卫,(x) 的儿子 (to) 是守卫

这是最复杂的情况,需要在 (son[x]) 选出一个 (dp[to][1]),而其他的儿子则是 (min(dp[to][1],dp[to][0]))

可以对所有儿子维护一个 (dp[to][1])(min(dp[to][1],dp[to][0])) 的差值 (dd),然后在最后把最小的差值 (dd_{min}) 加到 (dp[to][0]) 上即可。

于是 (dd={(dp[r][1]-min(dp[r][0],dp[to][1]))}^{r in son[x]}_{min},) (dp[to][0]=sum_{to in son[x]} min(dp[r][1],dp[r][0])+dd)

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
struct QAQ{int to,next;}a[1505]; 
int m,pan[1505],n,t,w[1505],dp[1505][3],head[1505];
inline void add(int x,int y){a[++t].to=y,a[t].next=head[x],head[x]=t;}
//dp[i][0] 自己不是守卫,父亲不是守卫,儿子是守卫 
//dp[i][1] 自己是守卫,  父亲不知道,  儿子不知道
//dp[i][2] 自己不是守卫,父亲是守卫,  儿子不知道 
inline void dfs(int x){
    R i,to,dd=0xfffffff;
    dp[x][1]=w[x];dp[x][2]=0;dp[x][0]=0;
    for(i=head[x];i;i=a[i].next){
        dfs(to=a[i].to);
        dd=min(dd,dp[to][1]-min(dp[to][0],dp[to][1]));//维护最小的差值 
        dp[x][0]+=min(dp[to][0],dp[to][1]);
        //若x守卫是儿子dp[x][0],找到花费最小的dd 加上其他的儿子:min(1.孙子dp[to][0]。2.自己dp[to][1]。) 
        dp[x][1]+=min(dp[to][1],dp[to][2]);
//若x有守卫dp[x][1],加上儿子:min(1.父亲dp[to][2]。2.自己dp[to][1]。) 
        dp[x][2]+=min(dp[to][0],dp[to][1]);
//若守卫是父亲dp[x][2],加上儿子:min(1.孙子dp[to][0]。2.自己dp[to][1]。) 
    }
    dp[x][0]+=dd;
}
int main(){
  memset(dp,127,sizeof(dp));
    scanf("%d",&n);
    R i,j,a,k,r;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&a,&k,&m);w[a]=k;
        for(j=1;j<=m;j++)scanf("%d",&r),pan[r]=1,add(a,r);
    }
    for(i=1;i<=n;i++)
        if(!pan[i]){
            dfs(i);
            printf("%d",min(dp[i][1],dp[i][0]));
            return 0;
        }
}
原文地址:https://www.cnblogs.com/Xing-Ling/p/11179420.html