题目传送门
【题目大意】
一棵有$n$个节点的树，每个节点$i$都有一个权值$A_i$。现在要把这棵树的节点全部染色，规则为：根节点$R$可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。每次染色的代价为$T*A_i$，其中$T$代表当前是第几次染色。求把这棵树染色的最小总代价。
【思路分析】
这题容易有一个错误的算法就是“每一步在可以被染色的点里选权值最大的染色”，我们明显可以构造出反例——一个权值很小的节点下面有很多权值巨大的节点，另一个权值较大的节点却没有子节点。不过我们可以从中提取出一个正确的性质：树中除根节点外权值最大的点，一定会在它的父节点被染色后立即染色。于是我们可以确定的是，树中权值最大的点及其父节点的染色操作是连续进行的，我们可以把这两个点“合并起来”。合并得到的新点的权值设为这两个点的权值的平均值。
于是贪心策略就是每次选择权值最大的点与其父亲节点合并，直到最后把整棵树合并成一个点，再按照顺序计算答案。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #define rg register 4 #define go(i,a,b) for(rg int i=a;i<=b;i++) 5 #define ll long long 6 using namespace std; 7 const int N=1002; 8 int n,root,fa[N],a[N],num[N]; 9 ll ans=0; 10 int main(){ 11 scanf("%d%d",&n,&root); 12 while(n&&root){ 13 go(i,1,n) scanf("%d",&a[i]),num[i]=1; 14 //num记录这个点所含原节点的数量 15 go(i,1,n-1){ 16 int x,y; 17 scanf("%d%d",&x,&y); 18 fa[y]=x; 19 } 20 go(i,1,n-1){ 21 double maxn=0;int now;//now记录要合并的节点 22 go(i,1,n) 23 if(i!=root&&1.0*a[i]/num[i]>=maxn)maxn=1.0*a[i]/num[i],now=i; 24 go(i,1,n) 25 if(fa[i]==now) fa[i]=fa[now]; 26 ans+=a[now]*num[fa[now]];//合并 27 num[fa[now]]+=num[now]; 28 a[fa[now]]+=a[now];a[now]=0; 29 } 30 ans+=a[root]; 31 printf("%lld\n",ans); 32 scanf("%d%d",&n,&root);ans=0; 33 } 34 return 0; 35 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11257688.html
相关资源：JAVA上百实例源码以及开源项目