win7 iis asp网站配置文件,网站推广方案,wordpress后台访问慢,开源 wordpress 主题$ POJ~2054~Color~a~Tree $ $ solution: $ 我们先从题中抽取信息#xff0c;因为每个点的费用和染色的次数有关#xff0c;所以我们可以很自然的想到先给权值大的节点染色。但是题目还说每个节点染色前它的父亲节点也必须被染色#xff0c;这就有了很多的后效性。 暂时没有办… $ POJ~2054~Color~a~Tree $ $ solution: $ 我们先从题中抽取信息因为每个点的费用和染色的次数有关所以我们可以很自然的想到先给权值大的节点染色。但是题目还说每个节点染色前它的父亲节点也必须被染色这就有了很多的后效性。 暂时没有办法贪心我们就只能再找找性质。博主首先想到的是从叶子节点考虑叶子节点里权值最小的一定最后染色。但是经过自我hack这个结论也是错的。举个栗子5-1-1-1-8这条链上如果以左边第一个1为根先染5会更优。 叶子节点我们拿他没办法所以我们看看树枝然后我们可以猜一个贪心对于某一个节点在它的所有儿子节点中最早被染色的一定是最大的那个。好吧这个贪心也是错的每个节点的费用会受到子节点的影响。 那什么情况下不会有后效性呢我们可以从全局考虑找整颗树上权值最大的节点这个节点一定在它父亲染色后第一个被染色。这个顺序绝不会变是一个正确的贪心。但是我们找到这个最大的节点之后又该如何找第二大的节点可这个结论还适用吗 这里我们有一个常用套路在之前贪心是我们其实就可以想到对每个点设定一个新的权值。但是这个设新权值的办法在最开始不好用它要猜。不过我们在想出上面这个贪心后就可以很容易设出来这个权值。因为上面说过了最大的节点一定在它父亲染色后第一个被染色。这我们不就相当与将两个点合并吗但是新权值怎么设我们仔细思考一下就可以知道新权值为新节点所包含节点的权值和除以包含的节点数 然后我们直接按照这个方法贪心找最大用优先队列每次合并时计算一下局部答案即可。复杂度 $ O(nlogn) $ $ code: $ #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset#define ll long long
#define db double
#define rg register intusing namespace std;db d[1005];
int n,root,top;
int s[1005];
int fa[1005];
int tot[1005];
int sum[1005];
int ans[1005];
bool use[1005];struct pi{db v; int id;inline bool operator (const pi x)const{return vx.v;}
}a[1005];priority_queuepi q;inline int qr(){register char ch; register bool sign0; rg res0;while(!isdigit(chgetchar()))if(ch-)sign1;while(isdigit(ch))resres*10(ch^48),chgetchar();if(sign)return -res; else return res;
}inline int get(int x){if(xs[x])return x;return s[x]get(s[x]);
}int main(){//freopen(.in,r,stdin);//freopen(.out,w,stdout);while(~scanf(%d%d,n,root)){if(!n!root)break;for(rg i1;in;i){rg xqr(); d[i]a[i].vx; a[i].idi; q.push(a[i]); //读入s[i]i; tot[i]1; use[i]0; sum[i]ans[i]x;//预处理} use[root]1; //根节点没有父亲不能合并所以直接判它已被使用for(rg i1;in;i){rg xqr(),yqr(); fa[y]x; //读入父子关系y}for(rg i1;in;i){ //有且仅有n-1次合并while(use[q.top().id]||d[q.top().id]!q.top().v)q.pop();//有一些节点被用过是无效的rg xq.top().id,yget(fa[x]); q.pop(); //x为儿子y为父亲s[x]y; use[x]1; ans[y]ans[x]sum[x]*tot[y]; //更新节点信息tot[y]tot[x]; sum[y]sum[x]; //更新节点信息pi z; d[y]z.v(db)sum[y]/tot[y]; z.idy; q.push(z); //合并节点}printf(%d\n,ans[root]); //根节点的答案才是最终答案}return 0;
} 转载于:https://www.cnblogs.com/812-xiao-wen/p/11249682.html
