洛谷 ~ P2458 [SDOI2006] ~ 保安站岗(树形DP,最小支配集变形)
注意他看守的是通道端点(即树中的点)
思路
看起来很像是最小点覆盖或最小支配集。但是最小点覆盖是去覆盖边的;最小支配集,一个点只可以被支配集中的一个点支配。而本题,需要支配点,但是一个点可以被多个点去支配,所以本题是最小支配集的一个变形。
表示以u为根的子树上的点全部被控制的答案。
表示,在u点安排一个保安,那么儿子什么状态都可以
表示,u点不放保安,但是u的父亲上有保安,那么儿子v可以被v的儿子结点控制,也可以被自身控制,但是不能被父节点控制,因为父节点是u,而u上没有保安
表示,u点不放保安,至少u的一个儿子结点上有保安。
对于来说,其实也就是所有儿子中至少有一个选,其他随便选。如果u的这棵子树的计算完毕了,dp[u][1]就是所有的儿子结点随便选,那么枚举一下儿子结点计算一下就是dp[u][2]
所以状态转移方程为:
但是注意需要在dp[u][1]计算结束之后才能去更新
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1505;
const int INF = 0x3f3f3f3f;
int n, a[MAXN], dp[MAXN][3];
vector<int> G[MAXN];
void dfs(int u, int fa)
{
dp[u][0] = a[u];
dp[u][1] = 0;
dp[u][2] = INF;
for (auto v : G[u])
{
if (v == fa) continue;
dfs(v, u);
dp[u][0] += min(min(dp[v][0], dp[v][1]), dp[v][2]); //u安排保安,儿子可以是任意状态
dp[u][1] += min(dp[v][0], dp[v][2]); //u不安排保安,但是u的父亲有保安,那么v可以被子结点控制,也可以由自己控制
}
for (auto v : G[u])
{
if (v == fa) continue;
dp[u][2] = min(dp[u][2], dp[u][1] - min(dp[v][0], dp[v][2]) + dp[v][0]); //u不安排保安,但是u至少有一个儿子有保安
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int u, v, k; scanf("%d", &u); scanf("%d%d", &a[u], &k);
while (k--)
{
scanf("%d", &v);
G[u].push_back(v);
G[v].push_back(u);
}
}
dfs(1, -1);
printf("%d\n", min(dp[1][0], dp[1][2]));
return 0;
}
/*
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
*/