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

P2458 [SDOI2006] 保安站岗

题目描述

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

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

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

编程任务：

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

输入格式

第 \(1\) 行 \(n\)，表示树中结点的数目。

第 \(2\) 行至第 \(n+1\) 行，每行描述每个通道端点的信息，依次为：该结点标号 \(i\)（\(0<i \le n\)），在该结点安置保安所需的经费 \(k\)（\(1\le k \le 10000\)），该边的儿子数 \(m\)，接下来 \(m\) 个数，分别是这个节点的 \(m\) 个儿子的标号 \(r_1,r_2,\cdots, r_m\)。

对于一个 \(n\)（\(0<n \le 1500\)）个结点的树，结点标号在 \(1\) 到 \(n\) 之间，且标号不重复。

输出格式

输出一行一个整数，表示最少的经费。

输入输出样例 #1

输入 #1

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

输出 #1

25

说明/提示

样例解释

在结点 \(2,3,4\) 安置 \(3\) 个保安能看守所有的 \(6\) 个结点，需要的经费最小：\(25\)。

---

解题报告

题目大意：在一棵有点权的树上选择一些点，一个被选择的点可以将它自己和所有与它相连的点覆盖，求出当整棵树都被覆盖时，所选点的权值和的最小值。

一道很不错的树上背包问题。

直接上树形 DP，考虑到当整棵树都被覆盖时，每个点 \(u\) 的状态就只有 \(3\) 种：

\(1\).节点 \(u\) 被选中。

\(2\).节点 \(u\) 未被选中，但被它的父节点 \(fa\) 覆盖。

\(3\).节点 \(u\) 未被选中，但被它的子节点 \(v\) 覆盖。

所以我们设状态方程 \(dp[u][0/1/2]\)，表示以节点 \(u\) 为根的子树全被覆盖时，\(u\) 处于分别处于那种覆盖情况。

设 \(w_u\) 表示节点 \(u\) 的权值，接下来具体考虑怎么从节点 \(u\) 的子节点转移到 \(v\)。

对于状态 \(1\)，由于节点 \(u\) 被选中，我们就可以没有限制的选择子节点 \(v\) 的状态，于是有：

\[dp[u][0]=w_u+\sum_{v \in son(u)} \min(dp[v][0],dp[v][1],dp[v][2]) \]

对于状态 \(2\)，由于节点 \(u\) 未被选中，它的子节点不存在被父节点覆盖的情况，于是有：

\[dp[u][1]=\sum_{v \in son(u)} \min(dp[v][0],dp[v][1]) \]

状态 \(3\) 的转移是本题的难点，我们可以这样处理：先保证 \(u\) 的所有子节点都被覆盖，然后强制分配一个子节点 \(v\) 被选中，具体写法为：

先计算 \(cst\)，表示强制选中一个子节点 \(v\) 后产生的最小额外代价：

\[cst=\min_{v \in son(u)} (dp[v][0]-dp[v][1]) \]

然后计算 \(dp[u][2]\)：

\[dp[u][2]=\sum_{ v \in son(u) } \min(dp[v][0],dp[v][1])+cst \]

然后本题就解决了，DP的复杂度为 \(O(n)\)，给出代码：

（注意：以下代码中的状态 \(1\) 和 \(2\) 与题解中的相反）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=(1E+18)+10;
const int N=2001100;inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}vector<int> e[N];
int n,w[N];
int dp[N][3];void dfs(int u,int fa)
{for(auto v:e[u])// 处理 好维护的状态0和2{if(v==fa) continue;dfs(v,u);dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]) );dp[u][2]+=dp[v][1];}int sum=0,cst=INF;for(auto v:e[u])// 维护 状态1{if(v==fa) continue;int tmp=min(dp[v][0],dp[v][1]);cst=min(cst,dp[v][0]-tmp);sum+=tmp;}dp[u][1]=sum+cst;
}signed main()
{n=read();for(int i=1;i<=n;i++){int u=read();w[u]=read();int m=read();for(int j=1;j<=m;j++){int v=read();e[u].push_back(v);e[v].push_back(u);}}for(int i=1;i<=n;i++){dp[i][0]=w[i];  // 放 保安dp[i][1]=INF;   // 不放保安且被子节点覆盖dp[i][2]=0;     // 不放保安且不被子节点覆盖}dfs(1,0);printf("%lld",min(dp[1][0],dp[1][1]));return 0;
}