题目内容

P3574

大意:村庄是一棵树,住在 1 号的管理要给每个房子送电脑,通过每个房子之间的道路需要 1 分钟,每个村民需要不同的时间安装电脑,而当管理把电脑送到村民后,村民会立即开始安装,最后管理会回到自己家给自己装电脑,求从管理出发到最后一个人装好电脑花费的时间。

解题思路

可以考虑每一个子树需要安装的最短时间。设住在 i 处的村民需要 c_i 的时间安装电脑, f_i 表示以 i 为根的子树全部安装好需要的最短时间,g_i 表示开车遍历以 i 为根的子树需要的最短时间,则有如下的方程:

f_i=\max(c_i,f_j+g_i+1)\
g_i\leftarrow g_i+g_j+2

其中 ji 的子节点,且 g_i 是动态更新的,就是遍历 j 之前的所有子树需要花的总时间。意思就是,对于一个 i 为根的子树,显然,第一次到 i 点的时候就让这里的村民开始装电脑得到的肯定更优,用这个时间与后面遍历下面节点的时间相比,总花费的时间是两者中间取最大的。而 f_j+g_i+1 的意义为,遍历过 j 节点之前的所有子节点需要的时间和 g_i 加上 j 节点需要的最短时间 f_j,至于 +1 就是从 i 节点走到 j 节点的花费。

而至于为什么是 +1 而不是 +2,是因为 \forall i:f_i-g_i\ge1,即等待的时间必然大于等于 1,所以只需要考虑从 i 进入 j 的时间,即为 1,而返回来的 1 的时间是被 f_j 覆盖掉的

不难发现,遍历的顺序会影响最终的结果,所以考虑贪心:可以发现,f_i-g_i 这段时间就是拿来等待的,做过接水问题的都知道要先处理等待时间大的,于是在转移前将子节点按照 f_i-g_i 排序即可。

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn=500010;
int n,c[maxn],f[maxn],g[maxn],tmp[maxn];
vector<int> G[maxn];

inline void ins(int a,int b)
{
    G[a].push_back(b);
    G[b].push_back(a);
    return;
}

inline bool cmp(int x,int y)
{
    return f[x]-g[x] > f[y]-g[y];
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(now!=1)//管理员的电脑最后装
        f[now]=c[now];
    int cnt=0;
    for(auto i:G[now])
        if(i!=fa)
            dfs(i,now);
    //一定要先遍历后记录儿子节点,不然会被下面的节点覆盖掉
    for(auto i:G[now])
        if(i!=fa)
            tmp[++cnt]=i;
    sort(tmp+1,tmp+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
        f[now]=max(f[now],f[tmp[i]]+g[now]+1),
        g[now]+=g[tmp[i]]+2;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        c[i]=read();
    int a,b;
    for(int i=1;i<n;i++)
    {
        a=read(),b=read();
        ins(a,b);
    }
    dfs(1,0);
    printf("%d\n",max(c[1]+g[1],f[1]));//在最后也要注意
    return 0;
}
最后修改日期:2020年11月28日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。