【bzoj3829】[Poi2014]FarmCraft

2015.06.24 16:50 Wed | 33次阅读 | 旧日oi | 固定链接 | 源码

Description

mhy住在一棵有n个点的树的1号结点上,每个结点上都有一个妹子。
mhy从自己家出发,去给每一个妹子都送一台电脑,每个妹子拿到电脑后就会开始安装zhx牌杀毒软件,第i个妹子安装时间为Ci。
树上的每条边mhy能且仅能走两次,每次耗费1单位时间。mhy送完所有电脑后会回自己家里然后开始装zhx牌杀毒软件。
卸货和装电脑是不需要时间的。
求所有妹子和mhy都装好zhx牌杀毒软件的最短时间。N(2<=N<=5 00 000)

题解

嗯,一道树形dp+贪心……由于以前好像是见过类似的题,所以没有花费太多时间就搞定了。
令mx[i]表示以i为根的子树,遍历过所有节点之后的最短时间,这里的最短时间是指从根节点直接到i然后遍历i子树的时间。
显然叶节点mx[i]=w[i]+dep[i]。
然后考虑遍历的顺序,这是一个贪心的思想,考虑相邻两个人,如果 2*(dis[a]+1)+mx[b]>2*(dis[b]+1)+mxa
注意w[1]要最后算。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define N 500005
int w[N],dis[N],mx[N],a[N],cnt,n;
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x;
}
struct edge
{
    int to,next;
}e[N<<1];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
bool cmp(int a,int b)
{
    return 2*(dis[a]+1)+mx[b]<2*(dis[b]+1)+mx[a];
}
int max(int a,int b)
{
    if(a>b) return a;
    return b;
}
void dfs(int u,int f,int d)
{
    int i,sum=0;
    for(i=h[u];e[i].to;i=e[i].next)
    if(e[i].to!=f)
    {
        dfs(e[i].to,u,d+1);
        dis[u]+=dis[e[i].to]+1;
    }
    for(cnt=0,i=h[u];e[i].to;i=e[i].next)
    if(e[i].to!=f) a[++cnt]=e[i].to;
    sort(a+1,a+cnt+1,cmp);
    mx[u]=w[u]+d;
    for(i=1;i<=cnt;i++)
    {
        mx[u]=max(mx[u],sum+mx[a[i]]);
        sum+=2*(dis[a[i]]+1);
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) w[i]=read();
    for(int u,v,i=1;i<n;i++)
    {
        u=read();v=read();
        ae(u,v);ae(v,u);
    }
    dfs(1,0,0);
    cout<<max(mx[1],w[1]+(n-1)*2)<<endl;
}```