題目：http://www.wikioi.com/problem/1307/

題意：給你一個(gè)樹，上面有n個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)價(jià)值p，求一個(gè)n個(gè)節(jié)點(diǎn)的排列順序，是的Σi*p[i]最小（要求父節(jié)點(diǎn)一定要在子節(jié)點(diǎn)的前面）

分析：

首先如果沒(méi)有父節(jié)點(diǎn)和子節(jié)點(diǎn)，那么這題就是一道弱弱的排序題，根據(jù)排序不等式，策略就是p越大的就放越前面

雖然此題有了這樣的限制，但是肯定也希望P越大的在前面越好，那么對(duì)于一個(gè)點(diǎn)它能放的最大的在哪里呢？當(dāng)然是緊接在它父節(jié)點(diǎn)的位置后面！！！！

于是我們可以先把每個(gè)點(diǎn)的權(quán)值加入優(yōu)先隊(duì)列中去，從中找出一個(gè)最大的權(quán)值點(diǎn)，將其與父節(jié)點(diǎn)合并成一個(gè)新節(jié)點(diǎn)，那么關(guān)鍵是這個(gè)節(jié)點(diǎn)的權(quán)值怎么處理呢？取平均值！

http://www.cnblogs.com/rainydays/archive/2013/08/20/3271277.html

這里引用神犇的博客……

然后就很簡(jiǎn)單的用堆維護(hù)就行了……

轉(zhuǎn)載于:https://www.cnblogs.com/wmrv587/p/3847539.html

總結(jié)

以上是生活随笔為你收集整理的[wikioi 1307][poj 2054]欧少堆（乱搞）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。