HDU 3452 Bonsai(树形dp)
2024-10-20 21:11:30
Bonsai
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 33 Accepted Submission(s) : 13
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
After being assaulted in the parking lot by Mr. Miyagi following the "All Valley Karate Tournament", John Kreese has come to you for assistance. Help John in his quest for justice by chopping off all the leaves from Mr. Miyagi's bonsai tree!
You are given an undirected tree (i.e., a connected graph with no cycles), where each edge (i.e., branch) has a nonnegative weight (i.e., thickness). One vertex of the tree has been designated the root of the tree.The remaining vertices of the tree each have unique paths to the root; non-root vertices which are not the successors of any other vertex on a path to the root are known as leaves.Determine the minimum weight set of edges that must be removed so that none of the leaves in the original tree are connected by some path to the root.
You are given an undirected tree (i.e., a connected graph with no cycles), where each edge (i.e., branch) has a nonnegative weight (i.e., thickness). One vertex of the tree has been designated the root of the tree.The remaining vertices of the tree each have unique paths to the root; non-root vertices which are not the successors of any other vertex on a path to the root are known as leaves.Determine the minimum weight set of edges that must be removed so that none of the leaves in the original tree are connected by some path to the root.
Input
The input file will contain multiple test cases. Each test case will begin with a line containing a pair of integers n (where 1 <= n <= 1000) and r (where r ∈ {1,……, n}) indicating the number of vertices in the tree and the index of the root vertex, respectively. The next n-1 lines each contain three integers ui vi wi (where ui, vi ∈ {1,……, n} and 0 <= wi <= 1000) indicating that vertex ui is connected to vertex vi by an undirected edge with weight wi. The input file will not contain duplicate edges. The end-of-file is denoted by a single line containing "0 0".
Output
For each input test case, print a single integer indicating the minimum total weight of edges that must be deleted in order to ensure that there exists no path from one of the original leaves to the root.
Sample Input
15 15
1 2 1
2 3 2
2 5 3
5 6 7
4 6 5
6 7 4
5 15 6
15 10 11
10 13 5
13 14 4
12 13 3
9 10 8
8 9 2
9 11 3
0 0
Sample Output
16
Source
2009 Stanford Local ACM Programming Contest
题意:
形成一颗以r为根的树,让所有的叶子节点和r节点没有联系,切割一些边,使切割的边的值之和最小。
题解:
dp[i]表示以i节点为根节点,让叶子节点和i节点分开的最小代价。
#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
int x,w;
node(int a,int b){x=a; w=b;}
};
int n,r;
vector<node> mp[];
int dp[];
void dfs(int k,int fa,int w)
{
dp[k]=w;
int sum;
if (mp[k].size()== && k!=r) sum=;//如果已经到叶子节点了,那么要赋值最大,后面求出来的值在比较中才能有效。
else sum=;
for(int i=;i<mp[k].size();i++)
{
if (mp[k][i].x==fa) continue;
dfs(mp[k][i].x,k,mp[k][i].w);
sum+=dp[mp[k][i].x];
}
//printf("%d: %d\n",k,sum);
dp[k]=min(dp[k],sum);
}
int main()
{
while(~scanf("%d%d",&n,&r))
{
if (n== && r==) break;
for(int i=;i<=n;i++) mp[i].clear();
for(int i=;i<n;i++)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
mp[x].push_back(node(y,w));
mp[y].push_back(node(x,w));
}
memset(dp,,sizeof(dp));
dfs(r,-,);
printf("%d\n",dp[r]);
} return ;
}
最新文章
- SQL中部分语法整理
- *HDU3339 最短路+01背包
- 为什么不要使用Response.Close()
- JavaScript RegExp 对象(来自w3school)
- 石阶 VS 石像
- Android Service服务
- CCTableView 简单样例
- 第十四节,基本数据类型,列表list
- Angularjs^1.2.9 搜索关键字高亮显示
- Springmvc 中org.springframework.http.converter.json.MappingJackson2HttpMessageConverter依赖jackson包
- NewLife.XCode 上手指南2018版(二)增
- add two nums
- VB进行RGB分色
- 23.C++- 继承的多种方式、显示调用父类构造函数、父子之间的同名函数、virtual虚函数
- windows7家庭版,专业版,旗舰版,企业版版本区别
- Codeforces Round #454 Div. 1
- 主机性能监控之wmi 获取系统信息及内存性能信息
- C#绘制三角形并填充,使用winform实现qq聊天气泡
- python为什么叫胶水语言?python为什么是系统脚本?
- [Algorithm] Tree: Lowest Common Ancestor