暑假集训 || 树DP

树上DP通常用到dfs https://www.cnblogs.com/mhpp/p/6628548.html

POJ 2342

相邻两点不能同时被选经典题

f[0][u]表示不选u的情况数，此时v可选可不选

f[1][u]表示选u的情况数，此时v不选

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int SZ = ;

const int INF = 1e9+;

int f[][SZ];

int head[SZ], nxt[SZ], l[SZ], tot = ;

void build(int f, int t)

{

    l[++tot] = t;

    nxt[tot] = head[f];

    head[f] = tot;

}

void dfs(int u, int fa)

{

    for(int i = head[u];i;i = nxt[i])

    {

        int v = l[i];

        if(v == fa) continue;

        dfs(v, u);

        f[][u] += max(f[][v], f[][v]);

        f[][u] += f[][v];

    }

    return;

}

int main()

{

    int n;

    scanf("%d", &n);

    for(int i = ; i <= n; i++) scanf("%d", &f[][i]);

    while()

    {

        int u, v;

        scanf("%d %d", &u, &v);

        if(u ==  && v == ) break;

        build(u, v);

        build(v, u);

    }

    dfs(, );

    printf("%d\n", max(f[][], f[][]));

    return ;

}

URAL 1018

一个二叉树，每条边上都有一定的苹果，减去一些边使得剩下的苹果最多（要从叶子那儿开始剪

f[p][u]表示在u点及它的子树内一共选择p个点，能剩下的最多苹果数

边权不好处理，把它转移到点上

转移时考虑u点（根节点）一定选，在左儿子和右儿子中一共选p-1个，分别枚举即可

记忆化搜索，每次dfs时若这个f[p][u]之前已经算过，可以直接return这个值

struct Tree

{

    int lc, rc;

}tree[SZ];

queue<int> q;

int vis[SZ], hasc[SZ];

void bfs()

{

    q.push();

    vis[] = ;

    while(q.size())

    {

        int u = q.front(); q.pop();

        int flag = ;

        for(int i = head[u];i;i = nxt[i])

        {

            int v = l[i].t;

            hasc[u] = ;

            if(!vis[v])

            {

                vis[v] = ;

                a[v] = l[i].d;

                q.push(v);

                if(!flag) tree[u].lc = v;

                if(flag) tree[u].rc = v;

                flag++;

            }

        }

    }

    return;

}

int dfs(int u, int p)//以u为根的子树，保留p个点

{

    if(p == ) return ;

    if(f[p][u] > ) return f[p][u];

    if(!hasc[u]) return a[u];

    for(int i = ; i < p; i++)

    {

        f[p][u] = max(f[p][u], dfs(tree[u].lc, i) + dfs(tree[u].rc, p-i-) + a[u]);

    }

    return f[p][u];

}

int main()

{

    scanf("%d %d", &n, &Q);

    for(int i = ; i < n-; i++)

    {

        int u, v, w;

        scanf("%d %d %d", &u, &v, &w);

        build(u, v, w);

        build(v, u, w);

    }

    bfs();

    printf("%d\n", dfs(, Q+));

    return ;

}

最小支配集 && 最小点覆盖 && 最大独立集

https://www.cnblogs.com/Ash-ly/p/5783877.html

UVA 1218

选一些点，当一个点被选择的时候，它邻接的点就被覆盖了，要求每个点被覆盖有且仅有一次，问最少选多少个点

最小支配集

https://blog.csdn.net/wyjwyl/article/details/51447427

神奇。。。

const int SZ = ;

const int INF = 1e9+;

int f[][SZ];

int head[SZ], nxt[SZ], l[SZ], tot = ;

void build(int f, int t)

{

    l[++tot] = t;

    nxt[tot] = head[f];

    head[f] = tot;

}

/*

f[0][u] u选了

f[1][u] u不选，有一个v选了

f[2][u] u不选，v不选

*/

void dfs(int u, int fa)

{

    int sum = , inc = INF;

    bool flag = false;

    for(int i = head[u]; i; i = nxt[i])

    {

        int v = l[i];

        if(v == fa) continue;

        dfs(v, u);

        f[][u] += (min(f[][v], f[][v]));

        if(f[][v] <= f[][v])

        {

            sum += f[][v];

            flag = true;

        }

        else

        {

            sum += f[][v];

            inc = min(inc, f[][v] - f[][v]);

        }

        if(f[][v] != INF && f[][u] != INF) f[][u] += f[][v];

        else f[][u] = INF;//

    }

    if(inc == INF && !flag) f[][u] = INF;

    else

    {

        f[][u] = sum;

        if(!flag) f[][u] += inc;

    }

    return;

}

int main()

{

    int n;

    while()

    {

        scanf("%d", &n);

        memset(f, , sizeof(f));

        memset(head, , sizeof(head));

        tot = ;

        for(int i = ; i < n-; i++)

        {

            int u, v;

            scanf("%d %d", &u, &v);

            build(u, v);

            build(v, u);

        }

        for(int i = ; i <= n; i++) f[][i] = , f[][i] = ;

        dfs(, );

        printf("%d\n", min(f[][], f[][]));

        int tmp;

        scanf("%d", &tmp);

        if(tmp == -) break;

    }

    return ;

}

Codeforces 274B

题意：给一棵树，每个点都有权值，每次操作可以把含有1号点的子树所有点权+1或者-1，问最少操作多少次可以让所有点权值都为0

思路：把点1作为根，考虑树上DP，从叶子开始每个点都有sub或者add，表示在这个点要加或减多少

在每个点加减后会影响它的父亲节点，对父亲节点的影响可以取max（要求总的操作次数最少）

神奇的dfs嗯

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#include <queue>

#include <set>

#include <vector>

#include <string>

using namespace std;

typedef long long LL;

const int SZ = ;

LL v[SZ];

int head[SZ*], nxt[SZ*], l[SZ*], tot = ;

LL sub[SZ], add[SZ];

void build(int f, int t)

{

    l[++tot] = t;

    nxt[tot] = head[f];

    head[f] = tot;

}

void dfs(int u, int fa)

{

    for(int i = head[u];i;i = nxt[i])

    {

        int v = l[i];

        if(v != fa)

        {

            dfs(v, u);

            sub[u] = max(sub[u], sub[v]);

            add[u] = max(add[u], add[v]);

        }

    }

    v[u] = v[u] - sub[u] + add[u];

    if(v[u] > ) sub[u] += v[u];

    else add[u] -= v[u];

}

int main()

{

    int n;

    scanf("%d", &n);

    for(int i = ; i < n-; i++)

    {

        int x, y;

        scanf("%d %d", &x, &y);

        build(x, y);

        build(y, x);

    }

    for(int i = ; i <= n; i++)

        scanf("%I64d", &v[i]);

    dfs(, );

    printf("%I64d\n", add[] + sub[]);

    return ;

}

巴特西

暑假集训 || 树DP

最新文章

热门文章