$ POJ~2054~Color~a~Tree $

---

---

$ solution: $

我們先從題中抽取信息，因?yàn)槊總€(gè)點(diǎn)的費(fèi)用和染色的次數(shù)有關(guān)，所以我們可以很自然的想到先給權(quán)值大的節(jié)點(diǎn)染色。但是題目還說每個(gè)節(jié)點(diǎn)染色前它的父親節(jié)點(diǎn)也必須被染色，這就有了很多的后效性。

暫時(shí)沒有辦法貪心，我們就只能再找找性質(zhì)。博主首先想到的是從葉子節(jié)點(diǎn)考慮，葉子節(jié)點(diǎn)里權(quán)值最小的一定最后染色。但是經(jīng)過自我hack，這個(gè)結(jié)論也是錯(cuò)的。舉個(gè)栗子：5-1-1-1-8，這條鏈上如果以左邊第一個(gè)1為根，先染5會(huì)更優(yōu)。

葉子節(jié)點(diǎn)我們拿他沒辦法，所以我們看看樹枝，然后我們可以猜一個(gè)貪心：對(duì)于某一個(gè)節(jié)點(diǎn)，在它的所有兒子節(jié)點(diǎn)中最早被染色的一定是最大的那個(gè)。好吧，這個(gè)貪心也是錯(cuò)的，每個(gè)節(jié)點(diǎn)的費(fèi)用會(huì)受到子節(jié)點(diǎn)的影響。

那，什么情況下不會(huì)有后效性呢？我們可以從全局考慮，找整顆樹上權(quán)值最大的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)一定在它父親染色后第一個(gè)被染色。這個(gè)順序絕不會(huì)變（是一個(gè)正確的貪心）。但是我們找到這個(gè)最大的節(jié)點(diǎn)之后又該如何？找第二大的節(jié)點(diǎn)？可這個(gè)結(jié)論還適用嗎？

這里我們有一個(gè)常用套路，在之前貪心是我們其實(shí)就可以想到：對(duì)每個(gè)點(diǎn)設(shè)定一個(gè)新的權(quán)值。但是這個(gè)設(shè)新權(quán)值的辦法在最開始不好用，它要猜。不過我們?cè)谙氤錾厦孢@個(gè)貪心后就可以很容易設(shè)出來這個(gè)權(quán)值。因?yàn)樯厦嬲f過了最大的節(jié)點(diǎn)一定在它父親染色后第一個(gè)被染色。這，我們不就相當(dāng)與將兩個(gè)點(diǎn)合并嗎？但是新權(quán)值怎么設(shè)？我們仔細(xì)思考一下就可以知道新權(quán)值為新節(jié)點(diǎn)所包含節(jié)點(diǎn)的權(quán)值和除以包含的節(jié)點(diǎn)數(shù)

然后我們直接按照這個(gè)方法貪心，找最大用優(yōu)先隊(duì)列，每次合并時(shí)計(jì)算一下局部答案即可。復(fù)雜度 $ O(nlogn) $

---

---

$ code: $

#include<iostream> #include<cstdio> #include<iomanip> #include<algorithm> #include<cstring> #include<cstdlib> #include<ctime> #include<cmath> #include<vector> #include<queue> #include<map> #include<set>#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 v<x.v;} }a[1005];priority_queue<pi> q;inline int qr(){register char ch; register bool sign=0; rg res=0;while(!isdigit(ch=getchar()))if(ch=='-')sign=1;while(isdigit(ch))res=res*10+(ch^48),ch=getchar();if(sign)return -res; else return res; }inline int get(int x){if(x==s[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 i=1;i<=n;++i){rg x=qr(); d[i]=a[i].v=x; a[i].id=i; q.push(a[i]); //讀入s[i]=i; tot[i]=1; use[i]=0; sum[i]=ans[i]=x;//預(yù)處理} use[root]=1; //根節(jié)點(diǎn)沒有父親，不能合并，所以直接判它已被使用for(rg i=1;i<n;++i){rg x=qr(),y=qr(); fa[y]=x; //讀入父子關(guān)系y}for(rg i=1;i<n;++i){ //有且僅有n-1次合并while(use[q.top().id]||d[q.top().id]!=q.top().v)q.pop();//有一些節(jié)點(diǎn)被用過，是無效的rg x=q.top().id,y=get(fa[x]); q.pop(); //x為兒子，y為父親s[x]=y; use[x]=1; ans[y]+=ans[x]+sum[x]*tot[y]; //更新節(jié)點(diǎn)信息tot[y]+=tot[x]; sum[y]+=sum[x]; //更新節(jié)點(diǎn)信息pi z; d[y]=z.v=(db)sum[y]/tot[y]; z.id=y; q.push(z); //合并節(jié)點(diǎn)}printf("%d\n",ans[root]); //根節(jié)點(diǎn)的答案才是最終答案}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/812-xiao-wen/p/11249682.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2054 Color a Tree (贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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