刷题记录:牛客NC24953[USACO 2008 Jan G]Cell Phone Network
admin
2024-02-03 10:06:12
0

传送门:牛客

题目描述:

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

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

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

主要思路:

  1. 首先这道题与那道战略游戏最大的不同就是那道题是覆盖树的边,而这道题是覆盖树的结点.注意,这两个问题是不一样的,比如这样的一颗树
1->2->3->4
如果只是为了覆盖结点的话我们可以选择2,3或者1,4,但是如果覆盖边的话我们就不能选择1,4这种情况了
  1. 所以我们需要使用dp[i][0/1/2]dp[i][0/1/2]dp[i][0/1/2]来记录三种状态(比那道题多一种状态)
    dp[i][0]dp[i][0]dp[i][0]代表当前结点放信号塔
    dp[i][1]dp[i][1]dp[i][1]代表当前结点不放信号塔,但是它的儿子放信号塔
    dp[i][2]dp[i][2]dp[i][2]代表当前结点不放信号塔,但是它的父亲放信号塔,这种情况类似于我之前局的栗子

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

dp[u][0]+=min(dp[v][0],dp[v][1],dp[v][2])dp[u][0]+=min(dp[v][0],dp[v][1],dp[v][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][2]+=min(dp[v][0],dp[v][1])dp[u][2]+=min(dp[v][0],dp[v][1])

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

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

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

dp[vj][0]+dp[v_j][0]+dp[vj​][0]+∑min(dp[vi][0],dp[vi][1])\sum\limits{min(dp[v_i][0],dp[v_i][1])}∑min(dp[vi​][0],dp[vi​][1]) i不等于j

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

dp[vj][0]−min(dp[vj][0],dp[vj][1])dp[v_j][0]-min(dp[v_j][0],dp[v_j][1])dp[vj​][0]−min(dp[vj​][0],dp[vj​][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];
vectoredge[maxn];
void dfs(int u,int per_u) {int m_son=0;dp[u][0]=1;for(int i=0;iint 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])m_son=v;}}dp[u][1]=dp[m_son][0];for(int i=0;iint 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<

相关内容

热门资讯

金庸小说多次被翻拍,为何无人去... 金庸小说多次被翻拍,为何无人去翻拍《风云》?这部剧的剧情迎合了十多年前观众的喜爱心理,却无法抓住如今...
这个是什么成语? 这个是什么成语?这个是什么成语?作鸟兽散 [zuò niǎo shòu sàn] [释义...
工作和玩户外两不误的成语? 工作和玩户外两不误的成语?劳逸结合 统筹兼顾
古代名字有姓有名,还有字、号、... 古代名字有姓有名,还有字、号、什么的,是什么意思?那是对某个人在不同场合不同关系人的称呼比如:在家你...
龙族的分类 龙族的分类龙1龙2龙3
咚咚咚 啦 啦啦啦啦 啦啦啦啦... 咚咚咚 啦 啦啦啦啦 啦啦啦啦 啦啦啦啦 这首歌还是曲啊叫什么 杉杉来了里面有坐在巷口...
女孩子是扁头好看还是圆头好看? 女孩子是扁头好看还是圆头好看?1 小孩子刚出生的时候没岁呢,头型都比较罩察游软,如果说家里有条件有很...
有没有好看的关于女扮男装的电视... 有没有好看的关于女扮男装的电视剧或电影花样少年少女新白娘子传奇花样少年少女,超级搞笑。
伊犁之美:7天6晚纯玩之旅,探... 伊犁之美:7天6晚纯玩之旅,探索夏塔古道与琼库什台 新疆旅游咨询: 小敏18509915393 小钰...
八年级生物,地理,物理的知识重... 八年级生物,地理,物理的知识重点归纳!详细一点!最好附带练习题!~拜托各位了!!谢谢!!!!问问老师...
北京五天四夜具体行程,北京5日... 北京,这座承载着千年历史与现代文明交相辉映的城市,一直以来都是我心中的旅游圣地。作为中国的首都,它不...
孩子们打架大人会如何处理呢? 孩子们打架大人会如何处理呢?孩子吵架大人闹后续如下:在一个秋高气爽的早晨,小明和小刚在草坪上玩游戏,...
中译云文化旅游:北京历史之旅,... 中译云:北京历史之旅,故宫长城 踏上北京的历史之旅,我们首先会被这座城市深厚的历史底蕴和丰富的文化遗...
为旅程加份安心:给暑期出国人群... 随着高考、中考、小升初以及各毕业考试的结束,令很多人翘首以盼的暑假即将来临。有些人在制定出国计划,比...
第二型曲线积分是什么? 第二型曲线积分是什么?第二型曲线积分是与曲线定向有关的曲线积分。第二型曲线积分亦称关于坐标的曲线积分...
孩子的格言 孩子的格言学习格言  战胜自己的困难,比在沙场上战胜敌人的战士更可以称为英雄。   ——倪张苗 ...
“连云港文旅总入口”2.0版正... “连云港文旅总入口” FUTURE TECHNOLOGY 科技焕新全域游玩体验 为进一步提升...
涠洲岛跟团游哪家线路最经典? 涠洲岛是中国创新的火山岛,以其独特的自然风光和丰富的海洋资源而闻名。近年来,越来越多的游客选择跟团游...
吕文扬和刘亚博观趵突泉“猪鲤”... 清晨的趵突泉畔,薄雾轻笼水面,三股清泉喷涌而出,溅起细碎的水花,发出清脆悦耳的声响。吕文扬和刘亚博穿...