【bzoj1596】[Usaco2008 Jan]电话网络 树形dp
网络 DP 树形 电话
2023-09-11 14:22:41 时间
题目描述
Farmer John决定为他的所有奶牛都配备手机,以此鼓励她们互相交流。不过,为此FJ必须在奶牛们居住的N(1 <= N <= 10,000)块草地中选一些建上无线电通讯塔,来保证任意两块草地间都存在手机信号。所有的N块草地按1..N 顺次编号。 所有草地中只有N-1对是相邻的,不过对任意两块草地A和B(1 <= A <= N; 1 <= B <= N; A != B),都可以找到一个以A开头以B结尾的草地序列,并且序列中相邻的编号所代表的草地相邻。无线电通讯塔只能建在草地上,一座塔的服务范围为它所在的那块草地,以及与那块草地相邻的所有草地。 请你帮FJ计算一下,为了建立能覆盖到所有草地的通信系统,他最少要建多少座无线电通讯塔。
输入
* 第1行: 1个整数,N
* 第2..N行: 每行为2个用空格隔开的整数A、B,为两块相邻草地的编号
输出
* 第1行: 输出1个整数,即FJ最少建立无线电通讯塔的数目
样例输入
5
1 3
5 2
4 3
3 5
样例输出
2
题解
树形dp。
f[x]表示子树x完全被覆盖,且x有信号塔的最小数量,
g[x]表示子树x完全被覆盖,且x无信号塔的最小数量,
h[x]表示子树x除x以外被覆盖的最小数量。
那么有f[x]=1+∑min(f[to[i]],g[to[i]],h[to[i]]),
h[x]=∑g[to[i]],
g[x]=∑min(f[to[i]],g[to[i]])+min(f[to[i]]-min(f[to[i]],g[to[i]])。
原理不难想,很好推。
最终答案为min(f[1],g[1])。
#include <stdio.h> #include <string.h> #define inf 0x07ffffff int to[20001] , next[20001] , head[10001] , f[10001] , g[10001] , h[10001] , cnt; int min(int a , int b) { return a < b ? a : b; } void add(int x , int y) { to[cnt] = y; next[cnt] = head[x]; head[x] = cnt ++ ; } void dp(int x , int last) { int i , y , sum = 0; f[x] = 1; g[x] = inf; for(i = head[x] ; i != -1 ; i = next[i]) { y = to[i]; if(y == last) continue; dp(y , x); f[x] += min(f[y] , min(g[y] , h[y])); h[x] += g[y]; sum += min(f[y] , g[y]); } for(i = head[x] ; i != -1 ; i = next[i]) { y = to[i]; if(y == last) continue; g[x] = min(g[x] , sum + f[y] - min(f[y] , g[y])); } } int main() { int n , i , x , y; scanf("%d" , &n); memset(head , -1 , sizeof(head)); for(i = 1 ; i <= n - 1 ; i ++ ) { scanf("%d%d" , &x , &y); add(x , y); add(y , x); } dp(1 , 0); printf("%d\n" , min(f[1] , g[1])); return 0; }
相关文章
- 【网络编程2】网络编程基础-发送ICMP包(Ping程序)
- 40行代码教你利用Python网络爬虫批量抓取小视频
- 推荐系统学习 -- 利用社交网络数据
- packetfence 7.2网络准入部署(二)
- 《android开发进阶从小工到专家》读书笔记--HTTP网络请求
- Leetcode1319. 连通网络的操作次数(medium,BFS,DFS)
- Leetcode2039. 网络空闲的时刻(medium, BFS)
- [OSI] 网络7层模型的理解
- DayDayUp:《机器崛起前传》第二十二章【蹒跚而来】读后感(文章源自网络)—听课笔记
- 低压配电网络中三相潮流计算的前推回代法(Matlab实现)
- hdu4405--Aeroplane chess(概率dp第七弹:飞行棋游戏--2012年网络赛)
- python基础===如何优雅的写代码(转自网络)
- 【算力网络】算力网络的发展趋势
- 2022年陕西省职业院校技能大赛“网络搭建与应用”赛项竞赛试题
- TSN网络设计与验证咨询服务