洛谷P2458 [SDOI2006]保安站岗 题解

题目链接：P2458 [SDOI2006]保安站岗

题意：

五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。

已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。

一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。

请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。

注意到这道题目可能会有相邻两个都不放保安的情况

首先想到记录一个结点是否放，以及其儿子、儿子的儿子是否放

但是这样比较麻烦

考虑设 \(dp[u][0/1/2]\) 表示 \(u\) 结点：

• \(0\) 表示被自己覆盖（自己放保安）
• \(1\) 表示被儿子覆盖（某个（或某些）儿子放保安）
• \(2\) 表示被父亲覆盖（父亲放保安）

容易推出 \(0,2\) 的转移方程 \[ dp[u][0]=\sum \min(dp[v][0/1/2])\\ dp[u][2]=\sum \min(dp[v][0/1]) \] 而 \(1\) 相对较麻烦

首先有从子结点的转移 \[ dp[u][2]=\sum \min(dp[v][0/1]) \] 但是如果所有的儿子都没有在他们自己那放保安，

则还要加上在在某个儿子放保安的最小花费

即 \[ \min(dp[v][0]-dp[v][1]) \] 为什么要减呢？因为在某个 \(v\) 放了保安后，就不用 \(dp[v][1]\) 的花费了

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
#define N (int)(2e3+15)

int n,val[N];
int dp[N][3];
vector<int> vec[N];
void addEdge(int u,int v)
{
    vec[u].push_back(v);
    vec[v].push_back(u);
}
void dfs(int u,int f)
{
    dp[u][0]=val[u];
    int ck=1,mn=INF;
    for(int v : vec[u])
    {
        if(v==f)continue;
        dfs(v,u);
        dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
        dp[u][1]+=min(dp[v][0],dp[v][1]);
        dp[u][2]+=min(dp[v][0],dp[v][1]);
        if(dp[v][0]<dp[v][1])ck=0;
        else mn=min(mn,dp[v][0]-dp[v][1]);
    }
    if(ck)dp[u][1]+=mn;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,m,v; i<=n; i++)
    {
        cin >> u >> val[u] >> m;
        for(int j=1; j<=m; j++)
            cin >> v,addEdge(u,v);
    }
    dfs(1,1);
    cout << min(dp[1][0],dp[1][1]) << endl;
    return 0;
}