P7840 「C.E.L.U-03」重构

moosssi · 2021-08-31 15:10:31 · 题解

首先，题目要求连 n-1 条边，那么每个点的 d_i 就至少为一 ，每连一条边 d_i 和会增加二，则总和就为 2n-2 ，减去每个点的，剩下的 d_i 就为 n-2 。

我们不用去考虑树的形态，只用去考虑如何分配剩下的 d_i 即可。

这里我就使用了优先队列，运用贪心思想每次取出 d_i+1 影响最小的点，统计答案后把它的 d_i+1 再加入队列，执行 n-2 这个过程就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,v[N],ans,d[N];
struct nod{
    int w,id;
    bool operator < (const nod t) const{
        return w>t.w;
    }
}p[N];
priority_queue<nod>q;
int get(int x){
    return v[x]*(2*d[x]+1);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
        ans+=v[i];
        d[i]=1;
        p[i].id=i;
        p[i].w=get(i);
        q.push(p[i]);
    }
    for(int i=1;i<=n-2;i++){
        nod temp=q.top();
        q.pop();
        ans+=temp.w;
        d[temp.id]++;
        p[temp.id].w=get(temp.id);
        q.push(p[temp.id]);
    }
    printf("%d",ans);
    return 0;
}