题目链接: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
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.
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).
#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的更多相关文章
-
hdu 4714 Tree2cycle dp
用树形dp做的,dp[t][i]表示t及其孩子入度都已经小于等于2并且t这个节点的入度等于i的最优解. 那么转移什么的自己想想就能明白了. 关键在于这个题目会暴栈,所以我用了一次bfs搜索出节点的顺序 ...
-
hdu 4714 Tree2cycle 树形经典问题
发现今天没怎么做题,于是随便写了今天杭电热身赛的一题. 题目:给出一棵树,删边和添边的费用都是1,问如何删掉一些树边添加一些树边,使得树变成一个环. 分析:统计树的分支数.大概有两种做法: 1.直接d ...
-
HDU 4704 Sum (2013多校10,1009题)
Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submi ...
-
HDU 4714 Tree2cycle(树状DP)(2013 ACM/ICPC Asia Regional Online ―― Warmup)
Description A tree with N nodes and N-1 edges is given. To connect or disconnect one edge, we need 1 ...
-
HDU 4714 Tree2cycle (树形DP)
Tree2cycle Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)Tot ...
-
HDU 4714 Tree2cycle (树形DP)
题意:给定一棵树,断开一条边或者接上一条边都要花费 1,问你花费最少把这棵树就成一个环. 析:树形DP,想一想,要想把一棵树变成一个环,那么就要把一些枝枝叶叶都换掉,对于一个分叉是大于等于2的我们一定 ...
-
HDU 4714 Tree2cycle(树型DP)
解题思路: 将一棵树变成一个环.假设一个结点的分叉数目大于等于2.则将它与父节点断开.而且断开子结点数目sum - 2条边,并再次连接sum-2个儿子形成一条直链然后这条游离链与还有一条游离链相连,共 ...
-
HDU 4714 Tree2cycle
Tree2cycle dfs 不是根节点:如果边数大于等于2,则删除与父节点的边.并且是一条环,那么每个点的度数是2,则还要删除num(每个节点儿子数)-2,只留两个儿子.当然删除边的儿子也要连到环上 ...
-
HDU 4714 Tree2cycle:贪心
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4714 题意: 给你一棵树,添加和删除一条边的代价都是1.问你将这棵树变成一个环的最小代价. 题解: 贪 ...
随机推荐
-
.NET程序的性能要领和优化建议
前几天在老赵的博客上看到,Bill Chiles (Roslyn 编译器的Program Manager)写了一篇文章叫做<Essential Performance Facts and .NE ...
-
C# 串口操作系列(3) -- 协议篇,二进制协议数据解析
原文地址:http://blog.csdn.net/wuyazhe/article/details/5627253 我们的串口程序,除了通用的,进行串口监听收发的简单工具,大多都和下位机有关,这就需要 ...
-
我利用网上代码开发的JQuery图片插件
我利用网上代码开发的JQuery图片插件 代码如下 (function($){ $.fn.FocusPic = function(options){ var defaults = { interval ...
-
delphi 获取颜色值的RGB
前言:http://www.cnblogs.com/studypanp/p/5002953.html 获取的颜色值 前面获取到一个像素点的颜色值后(十六进制),比如说(黄色):FFD1C04C(共八位 ...
-
Android开发之通过Intent启动其他App的Service
在Android5.0以前可以通过隐式Intent方式启动其他App的Service,就跟Activity启动隐式Intent一样的. 但是在5.0以后,只能使用显示的Intent方式启动了. 启动其 ...
-
《JavaScript高级程序设计 第3版》-学习笔记-1
P1-P30页 1.<script>标签的属性 async:async(html) | async="async"(xhtml),表示立即下载脚本,但不马上执行(执行 ...
-
[Locked] Sparse Matrix Multiplication
Given two sparse matrices A and B, return the result of AB. You may assume that A's column number is ...
-
DB2 递归
公司一直用递归来生成组织机构的树状图.看了上面的文档,应该立马就能写了. 不过前几天,有个功能涉及到下面的状况: 需要组织机构等级为1级的下面所有子机构.且按照一级组织机构分组.大家都觉得很难,哥就一 ...
-
给定N个整数集合是否存在两个其和刚好为指定常数的元素
又一次学习一遍<算法导论>,看到了这个问题: 描写叙述一个执行时间为O(nlgn)的算法,使之能在给定一个由n个整数构成的集合S和还有一个整数 X 时,推断出S中是否存在有两个其和刚好等于 ...
-
[#1] YCbCr与RGB的转换公式
1 YCbCr简介 YCbCr颜色空间是将RGB颜色空间进行坐标转换后得到的,常用于数字电视系统.Y取值范围:16~235 Cb.Cr的取值范围:16~240 YCbCr经常和YUV混淆.两者的主要差 ...