HDU 4714 Tree2cycle DP 2013杭电热身赛 1009

时间:2022-08-26 22:27:06

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4714

Tree2cycle

Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 400    Accepted Submission(s): 78

Problem Description
A tree with N nodes and N-1 edges is given. To connect or disconnect one edge, we need 1 unit of cost respectively. The nodes are labeled from 1 to N. Your job is to transform the tree to a cycle(without superfluous edges) using minimal cost.

A cycle of n nodes is defined as follows: (1)a graph with n nodes and n edges (2)the degree of every node is 2 (3) each node can reach every other node with these N edges.

 
Input
The first line contains the number of test cases T( T<=10 ). Following lines are the scenarios of each test case.
In the first line of each test case, there is a single integer N( 3<=N<=1000000 ) - the number of nodes in the tree. The following N-1 lines describe the N-1 edges of the tree. Each line has a pair of integer U, V ( 1<=U,V<=N ), describing a bidirectional edge (U, V).
 
Output
For each test case, please output one integer representing minimal cost to transform the tree to a cycle.
 
Sample Input
1
4
1 2
2 3
2 4
 
Sample Output
3
 
题目大意:已知一棵树,切边与连边都需要1的cost。现在要把这棵树分割连接成为一个环,求最小cost。
 
解题思路:将整棵树拆成N个单枝(所有点的度小于2),所需的cost即为2*N-1(拆成N个单枝需 N-1 cost,合成一个环需要 N cost)。
可用树形DP求出N最小的情况,用dp[i][j]表示以i为根的可用度为j的最小单枝数。
状态转移方程:dp[root][0]=min(dp[root][0]+dp[son][0],dp[root][1]+dp[son][1]-1)
       dp[root][1]=min(dp[root][1]+dp[son][0],dp[root][2]+dp[son][1]-1)
       dp[root][2]=dp[root][2]+dp[son][0]
P.S. 该题的数据量较大,要加#pragma comment(linker,"/STACK:1024000000,1024000000")语句,而且要用C++编译器,不能用G++。
 
 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
#define N 1000005
#define M 2000010
int vis[N],all,first[N],next[M],v[M],e,degree[N],dp[N][];
void addedge(int x,int y)
{
v[e]=y;
next[e]=first[x];
first[x]=e++;
}
void dfs(int root)
{
int i,k;
dp[root][]=dp[root][]=dp[root][]=;
vis[root]=;
for(i=first[root];i!=-;i=next[i])
{
k=v[i];
if(!vis[k])
{
dfs(k);
dp[root][]=min(dp[root][]+dp[k][],dp[root][]+dp[k][]-);
dp[root][]=min(dp[root][]+dp[k][],dp[root][]+dp[k][]-);
dp[root][]=dp[root][]+dp[k][];
}
}
}
int main()
{
int t,i,x,y;
scanf("%d",&t);
while(t--)
{
memset(dp,,sizeof(dp));
memset(first,-,sizeof(first));
e=;
all=;
int n;
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
memset(vis,,sizeof(vis));
dfs();
all=min(dp[][],min(dp[][],dp[][]));
// cout<<all<<endl;
printf("%d\n",all*-);
}
return ;
}

本人入ACM时间尚短,写的不好的地方请多见谅。

HDU 4714 Tree2cycle DP 2013杭电热身赛 1009的更多相关文章

  1. hdu 4714 Tree2cycle dp

    用树形dp做的,dp[t][i]表示t及其孩子入度都已经小于等于2并且t这个节点的入度等于i的最优解. 那么转移什么的自己想想就能明白了. 关键在于这个题目会暴栈,所以我用了一次bfs搜索出节点的顺序 ...

  2. hdu 4714 Tree2cycle 树形经典问题

    发现今天没怎么做题,于是随便写了今天杭电热身赛的一题. 题目:给出一棵树,删边和添边的费用都是1,问如何删掉一些树边添加一些树边,使得树变成一个环. 分析:统计树的分支数.大概有两种做法: 1.直接d ...

  3. HDU 4704 Sum (2013多校10&comma;1009题)

    Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submi ...

  4. HDU 4714 Tree2cycle(树状DP)(2013 ACM&sol;ICPC Asia Regional Online &horbar;&horbar; Warmup)

    Description A tree with N nodes and N-1 edges is given. To connect or disconnect one edge, we need 1 ...

  5. HDU 4714 Tree2cycle (树形DP)

    Tree2cycle Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)Tot ...

  6. HDU 4714 Tree2cycle &lpar;树形DP&rpar;

    题意:给定一棵树,断开一条边或者接上一条边都要花费 1,问你花费最少把这棵树就成一个环. 析:树形DP,想一想,要想把一棵树变成一个环,那么就要把一些枝枝叶叶都换掉,对于一个分叉是大于等于2的我们一定 ...

  7. HDU 4714 Tree2cycle&lpar;树型DP&rpar;

    解题思路: 将一棵树变成一个环.假设一个结点的分叉数目大于等于2.则将它与父节点断开.而且断开子结点数目sum - 2条边,并再次连接sum-2个儿子形成一条直链然后这条游离链与还有一条游离链相连,共 ...

  8. HDU 4714 Tree2cycle

    Tree2cycle dfs 不是根节点:如果边数大于等于2,则删除与父节点的边.并且是一条环,那么每个点的度数是2,则还要删除num(每个节点儿子数)-2,只留两个儿子.当然删除边的儿子也要连到环上 ...

  9. HDU 4714 Tree2cycle:贪心

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4714 题意: 给你一棵树,添加和删除一条边的代价都是1.问你将这棵树变成一个环的最小代价. 题解: 贪 ...

随机推荐

  1. &period;NET程序的性能要领和优化建议

    前几天在老赵的博客上看到,Bill Chiles (Roslyn 编译器的Program Manager)写了一篇文章叫做<Essential Performance Facts and .NE ...

  2. C&num; 串口操作系列&lpar;3&rpar; -- 协议篇,二进制协议数据解析

    原文地址:http://blog.csdn.net/wuyazhe/article/details/5627253 我们的串口程序,除了通用的,进行串口监听收发的简单工具,大多都和下位机有关,这就需要 ...

  3. 我利用网上代码开发的JQuery图片插件

    我利用网上代码开发的JQuery图片插件 代码如下 (function($){ $.fn.FocusPic = function(options){ var defaults = { interval ...

  4. delphi 获取颜色值的RGB

    前言:http://www.cnblogs.com/studypanp/p/5002953.html 获取的颜色值 前面获取到一个像素点的颜色值后(十六进制),比如说(黄色):FFD1C04C(共八位 ...

  5. Android开发之通过Intent启动其他App的Service

    在Android5.0以前可以通过隐式Intent方式启动其他App的Service,就跟Activity启动隐式Intent一样的. 但是在5.0以后,只能使用显示的Intent方式启动了. 启动其 ...

  6. 《JavaScript高级程序设计 第3版》-学习笔记-1

    P1-P30页 1.<script>标签的属性 async:async(html)  | async="async"(xhtml),表示立即下载脚本,但不马上执行(执行 ...

  7. &lbrack;Locked&rsqb; Sparse Matrix Multiplication

    Given two sparse matrices A and B, return the result of AB. You may assume that A's column number is ...

  8. DB2 递归

    公司一直用递归来生成组织机构的树状图.看了上面的文档,应该立马就能写了. 不过前几天,有个功能涉及到下面的状况: 需要组织机构等级为1级的下面所有子机构.且按照一级组织机构分组.大家都觉得很难,哥就一 ...

  9. 给定N个整数集合是否存在两个其和刚好为指定常数的元素

    又一次学习一遍<算法导论>,看到了这个问题: 描写叙述一个执行时间为O(nlgn)的算法,使之能在给定一个由n个整数构成的集合S和还有一个整数 X 时,推断出S中是否存在有两个其和刚好等于 ...

  10. &lbrack;&num;1&rsqb; YCbCr与RGB的转换公式

    1 YCbCr简介 YCbCr颜色空间是将RGB颜色空间进行坐标转换后得到的,常用于数字电视系统.Y取值范围:16~235 Cb.Cr的取值范围:16~240 YCbCr经常和YUV混淆.两者的主要差 ...