Java教程

树形dp/树的遍历

本文主要是介绍树形dp/树的遍历，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

牛客小白月赛45 E筑巢

题目链接：
https://ac.nowcoder.com/acm/contest/11222/E
题意概述：
给一棵n个节点的树，有边权和点权，权值可能为负，要求在树中取一个连通块，使该连通块的权值最大。
解析：
树形dp模板题。用f[i]表示以i为根的子树的权值最大值，可以选择一个连通块意味着在状态转移时，如果i的孩子f[j]为负，则可以不选这个孩子，或者将这个孩子的权值看作是0.
dfs过程：

  • 首先将i点的权值设置为f[i]的答案，然后遍历所有的孩子，dfs出孩子的权值f[j],f[i] += max(0, f[j]);
  • 注意是一棵树的遍历，所以dfs的时候传参是传u和fa，遍历孩子的时候，如果孩子==father，就continue.
    Ac代码
点击查看代码 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
const int N = 1e5 + 10;
const int M = 2 * N;
 
int n;
ll h[N], e[M], ne[M], w[M], idx;
ll f[N], val[N];
 
void add(ll a, ll b, ll c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a]= idx ++;
}
 
void dfs(ll u, ll fa){
    f[u] = val[u];
    for(int i = h[u]; i != -1; i = ne[i]){
        ll j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        f[u] += max(0ll, f[j] + w[i]);
    }
}
 
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%lld", &val[i]);
 
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i ++){
        ll x, y, z;
        scanf("%lld%lld%lld", &x, &y, &z);
        add(x, y, z), add(y, x, z);
    }
 
    dfs(1, -1);
 
    ll ans = -1e18;
    for(int i = 1; i <= n; i ++) ans = max(ans, f[i]);
 
    printf("%lld\n", ans);
 
    return 0;
}

Acwing 285. 没有上司的舞会

题目链接：
https://www.acwing.com/problem/content/287/
解析
好题。非常典型的树形dp。

  • 关于dp的具体过程

  • 关于树的遍历的一些思考

Ac代码

点击查看代码 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 6010;

int h[N], e[N], ne[N], idx;
int a[N], f[N][2], fa[N];
int n;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    f[u][1] = a[u];
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][1], f[j][0]);
        f[u][1] += f[j][0];
    }
    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        fa[a] = b;
    }
    int root = 0;
    for(int i = 1; i <= n; i ++)
        if(fa[i] == 0) {
            root = i;
            break;
        }
    
    dfs(root);
    
    printf("%d\n", max(f[root][1], f[root][0]));
    
    return 0;
}
这篇关于树形dp/树的遍历的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航