hdu5834Magic boy Bi Luo with his excited tree(树形DP)
发布时间：2021-01-24 12:14:04 所属栏目：大数据 来源：网络整理
导读：Magic boy Bi Luo with his excited tree Time Limit: 8000/4000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 823????Accepted Submission(s): 222 Problem Description Bi Luo is a magic boy,he also has a mi
|
Magic boy Bi Luo with his excited treeTime Limit: 8000/4000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 823????Accepted Submission(s): 222 Problem Description Bi Luo is a magic boy,he also has a migic tree,the tree has? You may attention that every? Now,Bi Luo define? Bi Luo is also an excited boy,now he wants to know every? Input First line is a positive integer? Four each test： The first line contain an integer? The next line contains? For the next? You can assume that the sum of? Output For the i-th test case,first output Case #i: in a single line,then output? Sample Input 1 5 4 1 7 7 7 1 2 6 1 3 1 2 4 8 3 5 2? Sample Output Case #1: 15 10 14 9 15? 这道题的题意就是给你一个树，每一个节点有一个收益，每条边每次经过都会有一个花费。问你从每个节点出发，最大的收益是多少。 这道题就是一个很明显的树形DP了，两个dfs，一个dfs是更新每个节点从当前节点出发回到原点的最大收益和不回到原点的最大收益，以及到达的位置。 第二个dfs是从父节点向下更新每个节点的答案。这个还是不难想的，就是细节有点多写起来有些烦。 AC代码： #include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1e5+5;
int head[maxn],tot,val[maxn];
int w[maxn],bw[maxn],wid[maxn],ans[maxn];
/*
w表示当前回来的最大收益
bw表示当前走出去的最大收益
id表示做出去的最大收益的节点
*/
void init(){
memset(head,-1,sizeof(head));
tot=0;
}
struct Edge{
int from,to,next,cost;
Edge(){}
Edge(int from,int to,int cost,int next){
this->from=from;
this->to=to;
this->cost=cost;
this->next=next;
}
}e[maxn*2];
void add_edge(int u,int v,int c){
e[tot]=Edge(u,v,c,head[u]);
head[u]=tot++;
e[tot]=Edge(v,u,head[v]);
head[v]=tot++;
}
void dfs1(int u,int fa){
w[u]=val[u];
bw[u]=val[u];
wid[u]=0;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
dfs1(v,u);
int btemp=max(0,bw[v]-e[i].cost*2);//回来的收益
int temp=bw[u]+max(0,w[v]-e[i].cost);//不回来的收益
w[u]+=btemp;
bw[u]+=btemp;
if(w[u]<temp){
w[u]=temp;
wid[u]=v;
}
}
}
void dfs2(int u,int fa,int sum1,int sum2){
//sum1表示当前节点不回来的最大收益，sum2表示当前节点回来的最大收益
ans[u]=max(w[u]+sum2,bw[u]+sum1);
int W=w[u];
int BW=bw[u];
int Id=wid[u];
W+=sum2;
if(W<=BW+sum1){
W=BW+sum1;
Id=fa;
}
BW+=sum2;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
if(v==Id){
int tmp1=sum1+val[u],tmp2=sum2+val[u];
for(int j=head[u];~j;j=e[j].next){
int vv=e[j].to;
if(vv==fa || v==vv) continue;
int tmp=max(0,bw[vv]-e[j].cost*2);
tmp1=max(tmp2+max(0,w[vv]-e[j].cost),tmp1+tmp);
tmp2+=tmp;
}
tmp1=max(0,tmp1-e[i].cost);
tmp2=max(0,tmp2-2*e[i].cost);
dfs2(v,tmp1,tmp2);
}
else{
int tmp=max(0,bw[v]-e[i].cost*2);
int tmp1=max(0,W-tmp-e[i].cost);
int tmp2=max(0,BW-tmp-e[i].cost*2);
dfs2(v,tmp2);
}
}
}
int main(){
int n,t,icas=1;
scanf("%d",&t);
while(t--){
init();
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
for(int i=1;i<n;i++){
int u,c;
scanf("%d%d%d",&u,&v,&c);
add_edge(u,c);
}
dfs1(1,-1);
dfs2(1,0);
printf("Case #%d:n",icas++);
for(int i = 1; i <= n; ++i)
printf("%dn",ans[i]);
}
}
（编辑：邯郸站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
