P2458 [SDOI2006]保安站岗 题解

xcxc82 · 2020-07-20 10:34:58 · 题解

P2458 [SDOI2006]保安站岗 题解

间隙(原题面)

• 前排声明:蒟蒻刚学OI没多久,讲的可能比较啰嗦,望见谅

大致题意

给一颗树,每个点都可以花费一定的价格来放置一名"保安"

每个保安都可以看管他本身所在的点和所有与他所站的点相邻的点

求:看管所有点所需要的最小花费

分析

树形dp。

先来说一种错误的做法,也是我一开始想到的做法

每个点都有"放置"和"不放置"两种选择

设dp[i][0]为第i个点"不放置"保安所需要的最小花费

dp[i][1]为第i个点“放置”保安所需要的最小花费

如果第i个点"放置"了保安

那它的下一个节点则可以选择"放或不放"两种决策

反之,下一个节点必须都"放置"一名保安

很明显是错的

放张图应该就明白了

(下一个节点不一定要由父亲或自己来看管,也可以由自己的"儿子"来看管)

也就是说,每个点的看管对象都有:

• 自己
• 父亲
• 儿子

三种可能

如何转移

设dp[i][0]为该点由自己看管所产生的最有解

(w[i]为父亲节点"放置"守卫所需要的价值)

• 2.由“父亲”看管

自己由父亲看管,说明自己所在的点上未"放置"门卫,那儿子肯定只能由自己的儿子看管或由自己看管

• 得到方程:dp[i][1]=\sum min(dp[son][0],dp[son][2])

• 3.由“儿子”看管

（图中红蓝分别为两种可能情况）

既然是由自己的儿子看管

儿子的决策也有两种可能

1.由儿子的"儿子"看管

2.由自己看管

• 得到方程:dp[i][2]=\sum min(dp[son][2],dp[son][0])

有一种极端情况,如果全部都选了dp[son][2]

"自己"就会产生无人看管的情况

因此要在这里加一个小特判,具体代码里有解释

这里做了个简陋的gif,不懂的可以结合代码看一下

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1510;
int n,dp[MAXN][4],w[MAXN];
int is_head[MAXN];
vector <int> son[MAXN];
void dfs(int x){
    bool is_cs = false;//用来判断有无极端情况

    int minn = 0x3ffffff;//用来求极端情况的最小值 
    dp[x][0] = w[x];
    for(int i=0;i<son[x].size();i++){
        int v = son[x][i];
        dfs(v);
        dp[x][0]+=min(min(dp[v][0],dp[v][1]),dp[v][2]);//由自己看守 
        dp[x][1]+=min(dp[v][2],dp[v][0]);//由父亲看守 
        //由儿子看守 ↓ 
        if(dp[v][0]<dp[v][2]){ 
            dp[x][2]+=dp[v][0];//如果儿子放置守卫花费的钱更少,那就直接在儿子的点上放置一个守卫 
            is_cs=true;//既然儿子的位置上已经放置守卫了,无极端情况存在 
        }
        else{//否则在儿子的儿子上放置守卫 
            minn = min( minn , dp[v][0]-dp[v][2]);//计算最小所需值 
            dp[x][2]+=dp[v][2];
        }
    }
    if(!is_cs) dp[x][2]+=minn;//如果存在极端情况,则加上差值,相当于是消掉dp[-][2],加上dp[-][0] 
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int u,m;
        scanf("%d%d",&u,&m);
        w[u]=m;
        int k;
        scanf("%d",&k);
        for(int i=1;i<=k;i++){
            int v;
            scanf("%d",&v);
            is_head[v]++;
            son[u].push_back(v);
        }
    }
    for(int i=1;i<=n;i++){
        if(!is_head[i]){
            dfs(i);
            cout<<min(dp[i][0],dp[i][2]);
            return 0;
        }
    }
}