POI2014 FAR-FarmCraft 树形DP+贪心

题目链接 https://www.luogu.org/problem/P3574

题意

翻译其实已经很明确了

分析

这题一眼就是贪心啊,但贪心的方法要思索一下,首先是考虑先走时间多的子树,但不太现实,因为时间跟点的个数也有关系,而且很有可能另外一棵子树不去走会闲置很长时间,就是这棵子树本来可以走一遍然后在子树装软件的时候去走别的树,所以不能这么贪心。那,要怎么办呢?
对于一棵子树,我们必须要走的是跑路时间,而安装可以在去别的子树走的时候干,所以我们肯定要先弄安装时间-跑路时间最大的子树,因为这样的话,我们就可以在它安装的时候去弄别的子树,证明用反证法,先弄别的子树最后时长一定大于先弄它,所以跑完每一个子树后,把它的安装时间和跑路时间扔到堆里,最后把堆取完,就完了,状态转移方程\(DP[u]=max(DP[son]+g[u]+1)\),g数组记录的跑路时间。

细节问题

首先呢,longlong不需要,爆不掉。
然后是加边,加单向边会出问题,加完图可能不连通,所以只能加双向边,加双向边数组要开2倍啊啊啊啊啊,本蒟蒻忘开然后RE了,接着我把5e5改成了6e5,还RE,然后我以为递归炸了,调了半天,我是不是傻。。。。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=6e5+10;
struct Edge{
    int nxt,to;
}e[N<<1];
int Head[N],len;
void Ins(int a,int b){
    e[++len].to=b;e[len].nxt=Head[a];Head[a]=len;
}
struct Node{
    int f,siz;
    Node(){}
    Node(int a,int b){f=a,siz=b;}     
    bool operator < (const Node&A)const{
        return f-siz<A.f-A.siz;
    }
};
int dp[N],g[N],val[N],que[N];
void dfs(int u,int fa){
    priority_queue<Node> q;
    if(u-1)dp[u]=val[u];
    for(int i=Head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);q.push(Node(dp[v],g[v]));
    }
    while(!q.empty()){
        Node now=q.top();q.pop();
        dp[u]=max(dp[u],now.f+g[u]+1);
        g[u]+=now.siz+2;
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>val[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        Ins(a,b);Ins(b,a);
    }
    dfs(1,0);
    cout<<max(dp[1],val[1]+g[1]);
    return 0;
}
上一篇:Windows 网络通信套接字技术


下一篇:50种“Hello,World”写法,我能玩出花来~