自动搬运

查看原文

来自洛谷，原作者为

	Idvz **

搬运于2025-08-24 21:44:26，当前版本为作者最后更新于2017-05-05 19:13:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以用dfs递归找一找

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int SN = 100000 + 10;

LL f[SN], t[SN], c[SN], now[SN], head[SN];
LL n, ans, que[SN], num, root;

bool vis[SN];

struct Edge {
    int from,to,next;
}E[SN<<1];

void dfs(int u) {
    vis[u] = 1;
    for(int i = head[u]; i ;i = E[i].next) {
        if(vis[E[i].to])    continue;
        dfs(E[i].to);
        c[u] = min(c[u] , c[E[i].to]); //小贪心，更新树中最小的花费
        now[u] += now[E[i].to]; //更新一下当前以i为节点的子树中购买的个数
    }
    if(now[u] < t[u]) {
        ans += (t[u]-now[u]) * c[u]; //如果不够，接着买
        now[u] = t[u];
    }
}

void Add(int u,int v) {
    E[++num].from = u;
    E[num].to = v;
    E[num].next = head[u];
    head[u] = num;
}


int main() {

    scanf("%lld",&n);
    
    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld",&f[i],&t[i],&c[i]);
        if(f[i] != -1)
        Add(i,f[i]),Add(f[i],i); //加无向边
        else root = i;
    }

    dfs(root);
    
    printf("%lld\n",ans);
    
    return 0;

}