刷题记录:牛客NC24953[USACO 2008 Jan G]Cell Phone Network

传送门:牛客

题目描述:

John想让他的所有牛用上手机以便相互交流，他需要建立几座信号塔在N块草地中。已知与信号塔相邻的草地
能收到信号。给你N-1个草地(A，B)的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。
输入:
5
1 3
5 2
4 3
3 5
输出:
2
1
2
3
4
5
6
7
8
9
10

经典的树形dp的题目.与这道战略游戏类似

做这道之前可以先去做那道战略游戏

主要思路:

1. 首先这道题与那道战略游戏最大的不同就是那道题是覆盖树的边,而这道题是覆盖树的结点.注意,这两个问题是不一样的,比如这样的一颗树

1->2->3->4
如果只是为了覆盖结点的话我们可以选择2,3或者1,4,但是如果覆盖边的话我们就不能选择1,4这种情况了
1
2

2. 所以我们需要使用$dp[i][0/1/2]$来记录三种状态(比那道题多一种状态)
   $dp[i][0]$代表当前结点放信号塔
   $dp[i][1]$代表当前结点不放信号塔,但是它的儿子放信号塔
   $dp[i][2]$代表当前结点不放信号塔,但是它的父亲放信号塔,这种情况类似于我之前局的栗子

所以我们可以写出以下转移:

$dp[u][0]+=min(dp[v][0],dp[v][1],dp[v][2])$

当前结点放信号塔,那么无论儿子是什么状态都是可以的

$dp[u][2]+=min(dp[v][0],dp[v][1])$

当前结点的父亲放信号塔,自己没有信号塔,所以儿子不能被自己管,但是儿子可以是除被自己管的其他状态

对于dp[u][1]的状态:

因为当前结点需要被自己的一个儿子管就行了,但是我们有很多个儿子,也就是说我们需要选出一个最佳的儿子.那么对于选择随意的一个儿子,我们有以下贡献:

$dp[v_j][0]+$$\sum min(dp[v_i][0],dp[v_i][1])$ i不等于j

那么我们随意的选择两个$j$,比较一下他们的关系,化简一下我们的式子,实际上就是比较

$dp[v_j][0]-min(dp[v_j][0],dp[v_j][1])$的值

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;int dp[10010][3];
vector<int>edge[maxn];
void dfs(int u,int per_u) {
	int m_son=0;dp[u][0]=1;
	for(int i=0;i<edge[u].size();i++) {
		int v=edge[u][i];
		if(v==per_u) continue;
		dfs(v,u);
		dp[u][0]+=min(dp[v][1],min(dp[v][0],dp[v][2]));
		dp[u][2]+=min(dp[v][1],dp[v][0]);
		if(dp[v][0]-min(dp[v][0],dp[v][1])<dp[m_son][0]-min(dp[m_son][0],dp[m_son][1])) {
			m_son=v;
		}
	}
	dp[u][1]=dp[m_son][0];
	for(int i=0;i<edge[u].size();i++) {
		int v=edge[u][i];
		if(v!=m_son&&v!=per_u) dp[u][1]+=min(dp[v][1],dp[v][0]);
	}
	return ;
}
int main() {
	n=read();int u,v;
	for(int i=1;i<=n-1;i++) {
		u=read();v=read();
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dp[0][0]=inf;
	dfs(1,0);
	cout<<min(dp[1][0],dp[1][1])<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59