洛谷 P2016 分析（别看）

科技起源的小号1

2026-10-15 21:21:56

发布于：天津

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：求一个最小值

1.2 题目背景、允许、禁止与限制

背景：有一个有 $n$ 个结点的无根树
允许：放置尽可能少的士兵，在结点 $i$ 放置士兵可以使所有与结点 $i$ 相连的边被监视
限制：最后要使整棵树的每条边都会被监视

1.3 题目数据范围与猜测

$1 \le d,n \le 1500 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一个无根树，可以放置一个士兵，在结点 $i$ 放置士兵可以使所有与结点 $i$ 相连的边被监视。最终求使整棵树的每条边都会被监视到的情况下需放置士兵的最小数量

2 题目破题推导

2.1 第一步：分情况考虑

首先我们知道，一条边 $E(u,v)$ 只可能被点 $u$ 或者点 $v$ 监视

如果点 $u$ 监视了，那么点 $v$ 就随意（点 $v$ 当然也可以监视，比如用于监视点 $v$ 的子节点）
如果点 $u$ 没有监视，那么点 $v$ 只能监视

3 模型匹配

提取关键词：
树+动态影响，是树形dp

4 具体方案

主要就是dp数组的定义
将 ${dp_i}_j(0 \le j \le 1)$ 设定为：以 $i$ 为根的子树，在结点 $i$ 放置（ $j=1$ ）以及不放置（ $j=0$ ）时所需的最小士兵数量
剩下的都比较简单

5 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 6e3 + 10;
int a[N];
vector<int> g[N];
int dp[N][2];
bool has_father[N];
void dfs(int u, int fa){
	dp[u][0] = 0, dp[u][1] = 1;
	for (int now : g[u]){
		if (now == fa){
			continue;
		}
		dfs(now, u);
		dp[u][0] += dp[now][1];
		dp[u][1] += min(dp[now][1], dp[now][0]);
	}
} 

int main(){
	
	memset(has_father, false, sizeof(has_father));
	cin >> n;
	for (int i = 1;i <= n;i++){
		int l, k;
		cin >> l >> k;
		for (int j = 1;j <= k;j++){
			int x;
			cin >> x;
			g[l].push_back(x);
			g[x].push_back(l);
			has_father[x] = true;
		}
	}
	dfs(1, -1);
	cout << min(dp[1][0], dp[1][1]);
	
	return 0;
}