首页 > 代码库 > 基础树形DP小结
基础树形DP小结
HDU 1520 Anniversary party
隔层选取,比较基础的树形DP了。
HDU 2196 Computer
我只想说一句这是毛线DP,明明是图论好么。
两次BFS求出权值和最大的一条链,再用两次BFS更新各点最大值。
搜了一下,真的有人用DP做,貌似更快一些。
#include <iostream> #include <algorithm> #include <cstdlib> #include <cstdio> #include <cstring> #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 int #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 1000000007 #define LM(a,b) (((ULL)(a))<<(b)) #define RM(a,b) (((ULL)(a))>>(b)) using namespace std; struct N { int u,v,w,next; }edge[1200000]; int head[10010]; int Top; void Link(int u,int v,int w) { edge[Top].u = u; edge[Top].v = v; edge[Top].w = w; edge[Top].next = head[u]; head[u] = Top++; } int dis[10010]; bool mark[10010]; struct Q { int w,v; bool operator < (const Q &a) const { return w < a.w; } }; int bfs(int s) { priority_queue<Q> q; Q f,t; f.w = 0,f.v = s; mark[s] = true; q.push(f); int Max = 0; int ep = s; while(q.empty() == false) { f = q.top(); q.pop(); if(f.w > Max) { ep = f.v; Max = f.w; } for(int p = head[f.v];p != -1; p = edge[p].next) { if(mark[edge[p].v] == false) { mark[edge[p].v] = true; t.v = edge[p].v; t.w = f.w + edge[p].w; q.push(t); } } } return ep; } void Cal_Max_Dis(int s) { priority_queue<Q> q; Q f,t; f.v = s; f.w = 0; mark[s] = true; q.push(f); while(q.empty() == false) { f = q.top(); q.pop(); if(dis[f.v] < f.w) { dis[f.v] = f.w; } for(int p = head[f.v];p != -1; p = edge[p].next) { if(mark[edge[p].v] == false) { mark[edge[p].v] = true; t.v = edge[p].v; t.w = f.w + edge[p].w; q.push(t); } } } } int main() { int n; int u,v; while(scanf("%d",&n) != EOF) { memset(head,-1,sizeof(int)*(n+2)); Top = 0; for(int i = 2;i <= n ; ++i) { scanf("%d %d",&u,&v); Link(i,u,v); Link(u,i,v); } memset(mark,false,sizeof(bool)*(n+2)); int e1 = bfs(1); memset(mark,false,sizeof(bool)*(n+2)); int e2 = bfs(e1); //cout<<e1<<" "<<e2<<endl; memset(dis,0,sizeof(int)*(n+2)); memset(mark,false,sizeof(bool)*(n+2)); Cal_Max_Dis(e1); memset(mark,false,sizeof(bool)*(n+2)); Cal_Max_Dis(e2); for(int i = 1;i <= n;++i) { printf("%d\n",dis[i]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。