hdu5834 Magic boy Bi Luo with his excited tree
转载声明:http://blog.csdn.net/cqu_hyx/article/details/52213912 题意: 个人感想: 好吧..我们直接进入主题,看看我对这题的理解.代码都是借鉴转载的..实在不会..增姿势吧.. dp[0][u]:代表从这个点出发,并且回到这个点的最大权值. 这是样例的图解. 首先我们最朴素的想法,肯定是从某些路径走去.然后不回来肯定值最大(包括只走到原来的位置,相当于不动). 那么我们可以酱紫先,首先我们全都回到原来的位置的最大值. 例如拿 1点来说,我们先走完所有子节点,并且获得的最大值dp[0][u]. 为什么我会在紫色的地方划线,因为肯定不选这条路啊,血亏… 那么我们怎么求到dp[1][u] 呢. 可是我们还有一种情况 例如第3点,可能先从5点走过去,再直接从父节点走过去的值更大呢.. 我们会想我们刚刚的过程,我们知道,树顶肯定可以知道怎么走,因为全子树都走过了. 那么我们是不是也可以通过dfs来记录父节点的dp[1][fa],dp[0][fa]的情况,再像dfs1一样求一遍不就行了 没错我们就是这样操作就行了只是递归时候得删除将要遍历的子节点的影响就可以得到父枝了. ╮(╯▽╰)╭,基本思想已经搞定了..希望能帮到那些比较难理解的朋友,我也尽力了..我得去学习了..画圈○. 分析:树形DP AC代码: /* Author:GavinjouElephant * Title: * Number: * main meanning: * * * */
#include <iostream>
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <cctype>
#include <vector>
#include <set>
#include <cstdlib>
#include <map>
#include <queue>
//#include<initializer_list>
//#include <windows.h>
//#include <fstream>
//#include <conio.h>
#define MaxN 0x7fffffff
#define MinN -0x7fffffff
#define lson 2*k
#define rson 2*k+1
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int Scan()//读入整数外挂.
{
int res = 0,ch,flag = 0;
if((ch = getchar()) == '-') //判断正负
flag = 1;
else if(ch >= '0' && ch <= '9') //得到完整的数
res = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9' )
res = res * 10 + ch - '0';
return flag ? -res : res;
}
void Out(int a) //输出外挂
{
if(a>9)
Out(a/10);
putchar(a%10+'0');
}
int T;
int N;
int val[maxn];
int head[maxn];
int dp[2][maxn];//0代表经过一些路,回到原来u点的最大值,1代表经过一些路,但不回来原来u点
int tot;
struct Edge
{
int to;
int w;
int nex;
};
Edge edge[2*maxn];
void addedge(int from,int to,int w)
{
edge[tot].to=to;
edge[tot].w=w;
edge[tot].nex=head[from];
head[from]=tot++;
}
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
void dfs1(int u,int fa)
{
dp[0][u]=dp[1][u]=val[u];
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa)continue;
dfs1(v,u);
if(dp[0][v]-2*edge[i].w>0)
{
dp[0][u]+=dp[0][v]-2*edge[i].w;
}
}
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa)continue;
int mx=dp[0][u]-max(0,dp[0][v]-2*edge[i].w)+(dp[1][v]-edge[i].w);
if(mx>=dp[1][u])
{
dp[1][u]=mx;
}
}
}
void dfs2(int u,int fa,int Cost) {
int dir = u,tmp;
if(fa != -1 && dp[0][fa] - Cost * 2 > 0)
{
dp[0][u] += dp[0][fa] - Cost * 2;
}
tmp = dp[1][u] = dp[0][u];
for(int i = head[u]; i!=-1; i = edge[i].nex)
{
int v = edge[i].to;
int mx=dp[0][u] - max(0,dp[0][v] - edge[i].w * 2) + (dp[1][v] - edge[i].w);
if(mx >= dp[1][u]) {
dir = v;
tmp=dp[1][u];
dp[1][u] = mx;
}
else if(mx >= tmp) {
tmp = mx;
}
}
// printf("dp[0][%d] = %d dp[1][%d] = %d tmp = %dn",u,dp[0][u],dp[1][u],tmp);
int L = dp[0][u],R = dp[1][u];
for(int i = head[u]; i!=-1; i = edge[i].nex)
{
int v = edge[i].to;
if(v == fa) continue;
int mx=dp[0][v] - edge[i].w * 2;
if(mx > 0)
{
dp[0][u]-= mx;
}
if(dir == v)
{
dp[1][u] = tmp;
}
if(dp[0][v] - edge[i].w * 2 > 0)
{
dp[1][u] -= mx;
}
// printf("dir = %dn",dir);
// printf("nxt%d = %dn",v,dp[1][u]);
dfs2(v,edge[i].w);
dp[0][u] = L,dp[1][u] = R;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("coco.txt","r",stdin);
freopen("lala.txt","w",stdout);
#endif
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
init();
printf("Case #%d:n",cas);
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&val[i]);
}
int u,w;
for(int i=1;i<N;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,w);
addedge(v,w);
}
dfs1(1,-1);
dfs2(1,0);
for(int i=1;i<=N;i++)
{
printf("%dn",max(dp[0][i],dp[1][i]));
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |