链接:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3659
题意:
有n(n≤10000)台机器形成树状结构。要求在其中一些机器上安装服务器,
使得每台不是服务器的计算机恰好和一台服务器计算机相邻。求服务器的最少数量。
分析:
按照每个结点的情况进行分类:
一、d(u,0):u是服务器,则每个子结点可以是服务器也可以不是。
二、d(u,1):u不是服务器,但u的父亲是服务器,这意味着u的所有子结点都不是服务器。
三、d(u,2):u和u的父亲都不是服务器。这意味着u恰好有一个儿子是服务器。
状态转移方程如下(其中v是u的子结点):
d(u,0) = sum{min(d(v,0), d(v,1))} + 1。
d(u,1) = sum(d(v,2))。
d(u,2)需要枚举当服务器的子结点编号v,然后把其他所有子结点v'的d(v',2)加起来,再和d(v,0)相加。
可以利用已经算出的d(u,1)写出一个新的状态转移方程:d(u,2) = min(d(u,1) – d(v,2) + d(v,0))。
最终答案为min(d(1,0), d(1,2))。
代码:
#include <cstdio>
#include <vector>
using namespace std; const int UP = + ;
int F[UP], d[UP][]; // F[r]为结点r的父结点
vector<int> seq, edge[UP]; // seq为结点访问顺序序列 void dfs(int r, int f){
F[r] = f;
seq.push_back(r);
for(int i = ; i < edge[r].size(); i++){
int b = edge[r][i];
if(b != f) dfs(b, r);
}
} int main(){
int n;
while(scanf("%d", &n) == ){
seq.clear();
for(int i = ; i <= n; i++) edge[i].clear();
for(int f, b, i = ; i < n; i++){
scanf("%d%d", &f, &b);
edge[f].push_back(b);
edge[b].push_back(f);
} dfs(, -); // 以结点1为根建立有根树
for(int p = seq.size() - ; p >= ; p--){
int r = seq[p];
d[r][] = ; d[r][] = ;
for(int i = ; i < edge[r].size(); i++){
int b = edge[r][i];
if(b == F[r]) continue;
d[r][] += min(d[b][], d[b][]); // d[r][0]代表r是服务器
d[r][] += d[b][]; // d[r][1]代表r不是服务器,但其父结点是
}
d[r][] = ; //d[r][2]代表r及其父结点都不是服务器
for(int i = ; i < edge[r].size(); i++){
int b = edge[r][i];
if(b == F[r]) continue;
d[r][] = min(d[r][], d[r][] - d[b][] + d[b][]);
}
}
printf("%d\n", min(d[][], d[][]));
scanf("%d", &n); // 读取结束标记
}
return ;
}
UVa 1218 - Perfect Service(树形DP)的更多相关文章
-
UVA - 1218 Perfect Service(树形dp)
题目链接:id=36043">UVA - 1218 Perfect Service 题意 有n台电脑.互相以无根树的方式连接,现要将当中一部分电脑作为server,且要求每台电脑必须连 ...
-
UVA - 1218 Perfect Service (树形dp)(inf相加溢出)
题目链接 题意:给你一个树形图,让你把其中若干个结点染成黑色,其余的染成白色,使得任意一个白色结点都恰好与一个黑色结点相邻. 解法比较容易,和树上的最大独立集类似,取一个结点作为树根,对每个结点分三种 ...
-
UVa 1218 - Perfect Service
/*---UVa 1218 - Perfect Service ---首先对状态进行划分: ---dp[u][0]:u是服务器,则u的子节点可以是也可以不是服务器 ---dp[u][1]:u不是服务器 ...
-
UVA - 1218 Perfect Service (树形DP)
思路:dp[i][0]表示i是服务器:dp[i][1]表示i不是服务器,但它的父节点是服务器:dp[i][2]表示i和他的父亲都不是服务器. 转移方程: d[u][0] += min(d[ ...
-
UVa 1218 Perfect Service 完美的服务
***状态设计值得一看dp[u][0]表示u是服务器(以下v均指任意u的子结点,son指u的所有子结点)ap[u][0]=sum{dp[v][1]}+1//错误,服务器是可以和其他服务器相邻的dp[u ...
-
POJ3398Perfect Service[树形DP 树的最大独立集变形]
Perfect Service Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 1518 Accepted: 733 De ...
-
UVa 10859 - Placing Lampposts 树形DP 难度: 2
题目 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&a ...
-
UVa 1292 - Strategic game (树形dp)
本文出自 http://blog.csdn.net/shuangde800 题目链接: 点击打开链接 题目大意 给定一棵树,选择尽量少的节点,使得每个没有选中的结点至少和一个已选结点相邻. 思路 ...
-
Uva LA 3902 - Network 树形DP 难度: 0
题目 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_pr ...
随机推荐
-
Dynamic CRM 2013学习笔记(四十六)简单审批流的实现
前面介绍过自定义审批流: Dynamic CRM 2013学习笔记(十九)自定义审批流1 - 效果演示 Dynamic CRM 2013学习笔记(二十一)自定义审批流2 - 配置按钮 Dynamic ...
-
(转载)MatLab绘图
转载自:http://www.cnblogs.com/hxsyl/archive/2012/10/10/2718380.html 转载自:http://www.cnblogs.com/jeromebl ...
-
register_globals(全局变量注册开关)
register_globals,是php.ini文件里面的一个配置选项,接下来,我们可以通过例程来分析一下,当register_globals = on 与 register_globals = o ...
-
用css控制一个DIV画图标。
在实际开发中,我们会用到一些小图形,图标.大多数情况下都是用图片来实现的,同时对图片进行处理使图片大小尽可能的缩小.但是图片在怎么处理也是按KB来算的.但是要是用CSS画,只要用很少的空间就能完成同样 ...
-
Java(基础)的类与变量
Java的类与成员变量 在我们学习编程语言中,需要灵活自用,那么怎么来灵活的将所有的函数属性来调用来实现完整的工程呢? 所以我们需要认识到类和变量的定义 1.类是什么? 类是抽象的概念,而对象就是类的 ...
-
JavaWeb三大组件之一Filter知识总结
[1] Filter简介 > Filter翻译为中文是过滤器的意思. > Filter是JavaWeb的三大web组件之一Servlet.Filter.Listener ...
-
python复杂网络库networkx:算法
http://blog.csdn.net/pipisorry/article/details/54020333 Networks算法Algorithms 最短路径Shortest Paths shor ...
-
json序列化NULL
在项目中遇到一问题,json序列化需要将null传递给前端,但之前项目中使用的都是fastjson的JSONObject.toJSONString(vo),这样会过滤掉为NULL的属性. 解决办法: ...
-
Go语言数组
目录 声明数组 数组在内存的结构 初始化数组 使用数组 函数间传递数组 数组使用注意事项 数组是具有相同唯一类型的一组已编号且长度固定的数据项序列(这是一种同构的数据结构);这种类型可以是任意的原始类 ...
-
IntelliJ IDEA 导航的 20 大特性
本文由 ImportNew - elviskang 翻译自 dzone.欢迎加入翻译小组.转载请见文末要求. 在前面的文章里,我介绍了IntelliJ IDEA(以下称IntelliJ)中与代码补全及 ...