1. 云图网首页
  2. 技术专区
  3. 编程笔记

算法提高课 第一章 动态规划 树形DP

• 编程笔记


求树的直径

image
image

1072. 树的最长路径

image
image

dfs

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010,M = 2*N;

int h[N],e[M],w[M],ne[M],idx;
int n,a,b,c;
int ans;

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

int dfs(int u,int fa) //求最大距离与次大距离
{
    int d1 = 0,d2 = 0;//d1表示最大距离，d2表示次大距离
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        int d = dfs(j,u) + w[i];
        if(d >= d1)
        {
            d2 = d1;
            d1 = d;
        }
        else if(d > d2)
        {
            d2 = d;
        }
    }
    ans = max(ans,d1+d2);//答案就是整棵树上的最大距离与次大距离的总和
    return d1;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d", &n);
    for (int i = 1; i < n; i ++ )
    {
        scanf("%d%d%d", &a, &b,&c);
        add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    cout<<ans<<endl;
    return 0;
}

DP写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010,M = 2*N;

int h[N],e[M],w[M],ne[M],idx;
int n,a,b,c;
int ans;
int f1[N],f2[N];//f1[u]、f2[u]:表示u到子树上某一点的最大距离
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u,int fa)
{
    f1[u] = 0,f2[u] = 0;
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j,u);
        int dist = f1[j] + w[i];
        if(dist >= f1[u])
        {
            f2[u] = f1[u];
            f1[u] = dist;
        }
        else if(dist >= f2[u])
        {
            f2[u] = dist;
        }
    }
    ans = max(ans,f1[u] + f2[u]);
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d", &n);
    for (int i = 1; i < n; i ++ )
    {
        scanf("%d%d%d", &a, &b,&c);
        add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    cout<<ans<<endl;
    return 0;
}

1073. 树的中心

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010,M = 2*N,INF = 0x3f3f3f3f;

int h[N], e[M],w[M], ne[M], idx;
int n;
int f1[N],f2[N];//f[i]:表示结点i向下到达其子树的结点中，距离的最大值和次大值
int fi[N];//fi[i]:表示结点i到达最大值结点时路径中经过的子节点
int up[N];//up[i]:表示结点i向上到达的距离的最大值
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dfs_d(int u,int fa)//向下dfs，求f1[u]和f2[u]，返回最大值f1[u]
{
    f1[u] = f2[u] = -INF;
    int dist = 0;
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dist = dfs_d(j,u) + w[i];
        if(dist > f1[u])//更新最大值
        {
            f2[u] = f1[u];
            f1[u] = dist;
            fi[u] = j;//注意更新最大值路径的经过的子节点
        }
        else if(dist > f2[u])//更新次大值
        {
            f2[u] = dist;
        }
    }
    if(f1[u] == -INF) f1[u] = f2[u] = 0;//没有更新过，说明是叶结点，向下的最大值与次大值为0
    return f1[u];
}

void dfs_u(int u,int fa)//自上而下求某结点经过其父节点的最远距离g[u]
{
    
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        if(j!=fi[u]) up[j] = max(up[u],f1[u]) + w[i];//子节点不在最大路径上，可以用父节点的最远距离更新
        else up[j] = max(up[u],f2[u]) + w[i];//子节点在最大距离路径上，只能用父节点的距离次大值更新
        dfs_u(j,u);
    }
}
int main()
{
    scanf("%d", &n);
    memset(h,-1,sizeof h);
    for (int i = 0; i < n-1; i ++ )
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    
    dfs_d(1,-1);
    dfs_u(1,-1);
    int ans = INF;
    for(int i = 1;i<=n;i++)
    {
        ans = min(ans,max(f1[i],up[i]));//最远距离为向上和向下中较大的，答案为最远距离的最小值
    }
    cout<<ans<<endl;
    return 0;
}

1075. 数字转换

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

const int N = 50010,M = 2*N,INF = 0x3f3f3f3f;

int h[N],e[M],w[M],ne[M],idx;
int n;
int f1[N],f2[N];//最远距离和次远距离
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
int sum(int x) //求x的约数(包括它本身)之和(1 + p + p^2 + ... + p^c1)*(1 + ... + p^c2)*...
{
    unordered_map<int,int>prime;//约数及其出现对次数
    for(int i = 2;i<=x/i;i++)//试除法求约数
    {
        while(x % i == 0)
        {
            prime[i]++;
            x = x/i;
        }
    }
    if(x > 1) prime[x]++;//处理大于sqrt(x)的约数
    
    int res = 1;
    for(auto t:prime)//求约数之和
    {
        int s = 1;//注意：s初始为1
        int p = t.first,e = t.second;
        while(e--)
        {
            s = s*p + 1;
        }
        res *= s;
    }
    return res;
}

int dfs(int u,int fa) //求树的直径
{
    int dist = 0;
    f1[u] = f2[u] = 0;
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dist = dfs(j,u) + w[i];
        if(dist > f1[u])
        {
            f2[u] = f1[u];
            f1[u] = dist;
        }
        else if(dist > f2[u])
        {
            f2[u] = dist;
        }
    }
    return f1[u];
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        int j = sum(i) - i;
      
        if(j < i && j>0) //题目要求约数之和小于本身且范围为正整数
        {
            add(i,j,1),add(j,i,1);
        }
    }
    dfs(1,-1);
    int ans = -1;
    for (int i = 1; i <= n; i ++ )
    {
        ans = max(ans,f1[i] + f2[i]);//最多变换次数就是树的直径
    }
    cout<<ans<<endl;
    return 0;
}

1074. 二叉苹果树

有依赖的分组背包问题+树形DP
image

image

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110,M = 2*N;
int n,q;
int h[N], e[M], w[M],ne[M], idx;
int f[N][N];//f[i][j]:以结点i为根的子树中，选择j个分支的所有方案的价值的最大值

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u,int fa)
{
    for(int i = h[u];i!=-1;i=ne[i]) //枚举物品组
    {
        if(e[i] == fa) continue;
        dfs(e[i],u);
        for(int j = q;j>=0;j--) //枚举体积,注意体积从大到小
        {
            for(int k = 0 ;k < j;k++) //枚举决策：每一组里选择哪些物品
            {
                f[u][j] = max(f[u][j],f[u][j - k - 1] + f[e[i]][k] + w[i]);//k-1预留出父节点的边
            }
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n-1; i ++ )
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1);
    cout<<f[1][q]<<endl;
    return 0;
}

323. 战略游戏

image
f[i,j]表示以结点i为根的子树中，j=1为选取结点i，j=0为不选取结点i
image
由于要选取树上的所有边，因此若不选结点i，则必须选取边的另一个端点s

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1510,M = N;

int h[N], e[M], ne[M], idx;
int n;
int f[N][2];
//f[i][0]:以结点i为根结点的子树中，不选结点i的所有方案中已选结点个数的最小值
//f[i][1]:以结点i为根结点的子树中，选择结点i的所有方案中已选结点个数的最小值
bool st[N]; //结点i是否有出度，找根结点用
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    f[u][0] = 0; //不选该结点，个数为0
    f[u][1] = 1; //选择该结点，个数为1
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += f[j][1];//不选该结点，就必须选另外一端点
        f[u][1] += min(f[j][0],f[j][1]);//选择该结点，另外一端点可以选也可不选，故选结点个数小的
    }
}

int main()
{
    while(scanf("%d", &n)!=-1)
    {
        memset(h, -1, sizeof h);
        idx = 0;//注意：初始化链表指针
        memset(st, 0, sizeof st);
        for (int i = 1; i <= n; i ++ )
        {
            int id,cnt;
            scanf("%d:(%d)",&id,&cnt);
            for(int j = 0;j<cnt;j++)
            {
                int b;
                scanf("%d", &b);
                add(id,b);
                st[b] = 1;
            }
        }
        int root = 0;
        while(st[root]) ++root;//找到没有出度的结点，即为根
        dfs(root);
        
        cout<<min(f[root][0],f[root][1])<<endl;//答案选个数小的
    }
    return 0;
}

1077. 皇宫看守

image

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1510,M = 2*N,INF = 0x3f3f3f3f;

int h[N], e[M], w[N],ne[M], idx;
int n;
bool st[N];
int f[N][3];
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b,ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    f[u][2] = w[u];
    
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        dfs(j);
        
        f[u][0] += min(f[j][1],f[j][2]);
        f[u][2] += min(min(f[j][0],f[j][1]),f[j][2]);
    }
    f[u][1] = INF;
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        f[u][1] = min(f[u][1],f[j][2] + f[u][0] - min(f[j][1],f[j][2]));
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        int id,cnt,cost;
        scanf("%d%d%d", &id, &cost,&cnt);
        w[id] = cost;
        while(cnt--)
        {
            int b;
            scanf("%d", &b);
            add(id,b);
            st[b] = 1;
        }
    }
    int root = 1;
    while(st[root]) ++root;
    dfs(root);
    cout<<min(f[root][1],f[root][2])<<endl;
    return 0;
}

原创文章，作者：kepupublish，如若转载，请注明出处：https://blog.ytso.com/273517.html

赞 (0)
0
上一篇 2022年7月11日
下一篇 2022年7月11日

相关推荐

发表回复

登录后才能评论