首页 > 代码库 > 【bzoj2466】[中山市选2009]树 树形dp
【bzoj2466】[中山市选2009]树 树形dp
题目描述
图论中的树为一个无环的无向图。给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的）。并且该节点的直接邻居也发生同样的变化。
开始的时候，所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。
输入
输入文件有多组数据。
输入第一行包含一个整数n，表示树的节点数目。每个节点的编号从1到n。
输入接下来的n – 1行，每一行包含两个整数x，y，表示节点x和y之间有一条无向边。
当输入n为0时，表示输入结束。
输出
对于每组数据，输出最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。
样例输入
3
1 2
1 3
0
样例输出
1
题解
网上很多题解是高斯消元，然而我不会O(n^3)的算法，只会O(n)的树形dp（手动滑稽）
设a[x]表示x按且x亮的最小次数，b[x]表示x不按且x亮的最小次数，c[x]表示x按且x不亮的最小次数，d[x]表示x不按且x不亮的最小次数。
那么如果父亲按（状态a、c），则儿子必须不亮（状态c、d）；如果父亲不按（状态b、d），则儿子必须亮（状态a、b）。
所以两个一组来转移，判断儿子的按与不按来更新。
状态转移方程有点复杂，自己慢慢体会~
注意最大值不能赋得过大，否则如果儿子全选择了最大值，那么会爆int。
#include <cstdio>#include <cstring>#include <algorithm>#define N 110using namespace std;int head[N] , to[N << 1] , next[N << 1] , cnt , a[N] , b[N] , c[N] , d[N];void add(int x , int y){ to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void dfs(int x , int fa){ int i , t; a[x] = 1 , d[x] = 0 , b[x] = c[x] = 100; for(i = head[x] ; i ; i = next[i]) { if(to[i] != fa) { dfs(to[i] , x); t = a[x] , a[x] = min(a[x] + d[to[i]] , c[x] + c[to[i]]) , c[x] = min(c[x] + d[to[i]] , t + c[to[i]]); t = b[x] , b[x] = min(b[x] + b[to[i]] , d[x] + a[to[i]]) , d[x] = min(d[x] + b[to[i]] , t + a[to[i]]); } }}int main(){ int n , i , x , y; while(scanf("%d" , &n) != EOF && n) { memset(head , 0 , sizeof(head)) , cnt = 0; for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x); dfs(1 , 0); printf("%d\n" , min(a[1] , b[1])); } return 0;}
【bzoj2466】[中山市选2009]树 树形dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。