首页 > 搜索 > DFS搜索 > HDU 3848-CC On The Tree-动态规划-[解题报告]HOJ
2015
04-13

HDU 3848-CC On The Tree-动态规划-[解题报告]HOJ

CC On The Tree

问题描述 :

CC lives on the tree which has N nodes.On every leaf of the tree there is an apple(leaf means there is only one branch connect this node ) .Now CC wants to get two apple ,CC can choose any node to start and the speed of CC is one meter per second.
  now she wants to know the shortest time to get two apples;

输入:

Thers are many cases;
  The first line of every case there is a number N(2<=N<=10000)
if n is 0 means the end of input.
Next there is n-1 lines,on the i+1 line there is three number ai,bi,ci
which means there is a branch connect node ai and node bi.
(1<=ai, bi<=N , 1<=ci<=2000)
ci means the len of the branch is ci meters ;

输出:

Thers are many cases;
  The first line of every case there is a number N(2<=N<=10000)
if n is 0 means the end of input.
Next there is n-1 lines,on the i+1 line there is three number ai,bi,ci
which means there is a branch connect node ai and node bi.
(1<=ai, bi<=N , 1<=ci<=2000)
ci means the len of the branch is ci meters ;

样例输入:

7
1 2 1
2 3 2
3 4 1
4 5 1
3 6 3
6 7 4
0

样例输出:

5

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

题目大意:给定一棵树,枝上都有一个权,求所有叶子间的最小距离(即求任意两叶子之间的最小距离)典型的树形DP,记录最大和次大即可。

代码如下:

#include <iostream>
#include <cstdio>

using namespace std;

const int inf=30000000;
const int maxx=10003;

struct Tree{
	int v,we,next;
};

Tree tree[maxx*2];
int head[maxx*2],pt;
int dp_f[maxx],dp_s[maxx];

void adde(int x,int y,int we){
	tree[pt].v=y;
	tree[pt].we=we;
	tree[pt].next=head[x];
	head[x]=pt++;
}

int min(int a,int b){
	return a<b?a:b;
}

void dfs(int root,int pre){//选出从每个根到其所有子树的叶子距离的最小值和次小值
	bool mark=false;
	for(int i=head[root];i;i=tree[i].next){
		int v=tree[i].v;
		if(pre==v)continue;
		mark=true;
		dfs(v,root);
		if(dp_f[root]>(dp_f[v]+tree[i].we)){
			dp_s[root]=dp_f[root];
			dp_f[root]=dp_f[v]+tree[i].we;
		}else if(dp_f[root]==dp_f[v]+tree[i].we){
			dp_s[root]=dp_f[root];
		}else{
            dp_s[root]=min(dp_s[root],dp_f[v]+tree[i].we);
		}
	}
	if(!mark)dp_f[root]=dp_s[root]=0;
}

int main(){
	int n;
	while(scanf("%d",&n)&&n){
		pt=1;
		int i,x,y,we,cnt;
		cnt=0;
		for(i=1;i<=n;i++){
			dp_f[i]=dp_s[i]=inf;
		}
		memset(head,0,sizeof(head));
		memset(tree,0,sizeof(tree));
		for(i=2;i<=n;i++){
			scanf("%d%d%d",&x,&y,&we);
			adde(x,y,we);
			adde(y,x,we);
			if(x==1 || y==1)cnt++;//这个地方在考虑根节点是否为叶子的时候只判断了x而没有判断y,wa了三次。悲剧
		}
		dfs(1,0);//把1当作根节点深搜
		int ans=1<<30;
		for(i=1;i<=n;i++){//选一遍最小的就可以了
			if(dp_f[i]==0 || dp_s[i]==0 ||dp_f[i]>20000000 ||dp_s[i]>20000000)continue;
			ans=min(ans,dp_f[i]+dp_s[i]);
		}
		if(cnt==1)ans=min(ans,dp_f[1]);//如果根结点是叶子的话,还得判断一下根节点处的情况
		printf("%d\n",ans);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/iaccepted/article/details/6738239


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。