首页 > 代码库 > SDUT2013级测试赛_D
SDUT2013级测试赛_D
题目描述
给出一棵含有n个点的树,每个点权值为wi,求从根节点到叶子结点权值和最大的那条路经的权值和是多少。
输入
n(1<= n && n <= 10000)。
接下来n+1行,每行两个整数w(w <= 1000)。
第i个节点的父节点为w,若 i为根节点。600组数据。
输出
对于每组数据,输出一个数代表答案。
示例输入
3 0 5 1 5 1 6
示例输出
11
提示
来源
解题报告
求从根节点出发到叶子的最长路。。。很像数塔。。。
我暴力dfs过了.怒搜所有数枝,搜完答案就有了。。。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { int v,next; } edge[100000]; int head[10010],cnt,vv[10010],vis[10010],n,maxx; void add(int u,int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int s,int d) { int i,j; for(i=head[s]; i!=-1; i=edge[i].next) dfs(edge[i].v,d+vv[edge[i].v]); if(d>maxx) maxx=d; } int main() { int i,j,v,w; while(~scanf("%d",&n)) { maxx=0; cnt=0; memset(edge,0,sizeof(edge)); memset(vv,0,sizeof(vv)); memset(head,-1,sizeof(head)); for(i=0; i<n; i++) { scanf("%d%d",&v,&w); add(v-1,i); vv[i]=w; } dfs(0,vv[0]); printf("%d\n",maxx); } return 0; }
学长标程好像跟数塔类似,从下至上的找最大的。。。
下面是啸爷的标程。。。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 9999991 using namespace std; int head[10010]; struct E { int v,next; }edge[10010]; int Top; int Link(int u,int v) { edge[Top].v = v; edge[Top].next = head[u]; head[u] = Top++; } int value[10010]; int dfs(int root) { int temp = 0; for(int p = head[root];p != -1; p = edge[p].next) { temp = max(temp,dfs(edge[p].v)); } value[root] += temp; return value[root]; } int main() { freopen("data1.in","r",stdin); freopen("data1.out","w",stdout); int n,i,j,v,w; while(scanf("%d",&n) != EOF) { memset(head,-1,sizeof(head)); Top = 0; for(i = 1;i <= n; ++i) { scanf("%d %d",&v,&w); Link(v,i); value[i] = w; } printf("%d\n",dfs(1)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。