話(huà)說(shuō)寧波市的中小學(xué)生在鎮(zhèn)海中學(xué)參加計(jì)算機(jī)程序設(shè)計(jì)比賽，比賽之余，他們?cè)阪?zhèn)海中學(xué)的各個(gè)景點(diǎn)參觀。鎮(zhèn)海中學(xué)共有n個(gè)景點(diǎn)，每個(gè)景點(diǎn)均有若干學(xué)生正在參 觀。這n個(gè)景點(diǎn)以自然數(shù)1至n編號(hào)，每?jī)蓚€(gè)景點(diǎn)的編號(hào)均不同。每?jī)蓚€(gè)景點(diǎn)之間有且只有一條路徑。選擇哪個(gè)景點(diǎn)集中所有的學(xué)生，才能使所有學(xué)生走過(guò)的路徑之和最小呢？

輸入描述：

　　第一行只有一個(gè)正整數(shù)n，表示景點(diǎn)數(shù)。

　　第二行有n個(gè)1至1000間的整數(shù)，這n個(gè)整數(shù)間互相以一個(gè)空格分隔。其中第i個(gè)整數(shù)表示第i個(gè)景點(diǎn)處的學(xué)生數(shù)。

　　第三行至第n+1，每行有三個(gè)整數(shù)i,j,k，表示景點(diǎn)i和景點(diǎn)j之間有一條長(zhǎng)為k的路徑直接連接。其中i<>j，1≤i≤n, 1≤j≤n；1≤k≤1000。

輸出描述：

　　有二行：

　　第一行只有一個(gè)整數(shù)i，表示在第i個(gè)景點(diǎn)處集中時(shí)，所有學(xué)生走過(guò)的路之和最短。

第二行也只有一個(gè)整數(shù)，表示所有學(xué)生走過(guò)的路徑之和的最小值

1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 int n,num[100002],a,b,c,g[100002],tot,cnt,poi;//poi為最優(yōu)點(diǎn) 9 long long ans[100002],minn=9223372036854775807,siz[100002];//siz[i]以i為根節(jié)點(diǎn)的樹(shù)的點(diǎn)權(quán)和，minn為最優(yōu)答案，ans[i]為以i為根時(shí)的答案 10 struct s1 11 {int t,next; 12 long long l; 13 } e[200002];//e是邊的相關(guān)信息，t是重點(diǎn)，next是下一條邊，l是邊權(quán) 14 void addedge(int s,int t,int l)//建圖 15 {e[++tot].next=g[s]; 16 g[s]=tot; 17 e[tot].t=t; 18 e[tot].l=l; 19 return; 20 } 21 void geta(int x,int d,int f)//預(yù)處理：隨便找個(gè)點(diǎn)（這里是1）作為根節(jié)點(diǎn)遍歷整棵樹(shù)，計(jì)算以這個(gè)點(diǎn)為根時(shí)的siz和ans 22 {siz[x]=num[x]; 23 for(int i=g[x];i!=0;i=e[i].next) 24 if(e[i].t!=f)//因?yàn)樽畛跏请p向建邊，所以這里應(yīng)注意不需要重復(fù)處理。又因?yàn)闃?shù)上沒(méi)有環(huán)，所以別再去找父節(jié)點(diǎn)就行 25 {geta(e[i].t,d+e[i].l,x); 26 siz[x]+=siz[e[i].t]; 27 ans[1]+=siz[e[i].t]*e[i].l; 28 } 29 return; 30 } 31 void dp(int x,int f) 32 {if(ans[x]<minn)//到達(dá)每個(gè)點(diǎn)時(shí)ans必然是已經(jīng)算好的，所以先更新minn和poi 33 {minn=ans[x]; 34 poi=x; 35 } 36 for(int i=g[x];i!=0;i=e[i].next)//計(jì)算好子節(jié)點(diǎn)的ans之后再將階段轉(zhuǎn)移到子節(jié)點(diǎn)，以繼續(xù)計(jì)算其他的ans 37 if(e[i].t!=f)//同樣不需要重復(fù)處理 38 {ans[e[i].t]=ans[x]+e[i].l*(cnt-2*siz[e[i].t]);//由ans[e[i].t]=ans[x]+(cnt-siz[e[i].t])*e[i].l-siz[e[i].t]*e[i].l化簡(jiǎn)而來(lái)，即以e[i].t為根的子樹(shù)上的點(diǎn)不需要再經(jīng)過(guò)第i條邊，其他點(diǎn)需要經(jīng)過(guò)第i條邊 39 dp(e[i].t,x); 40 } 41 return; 42 } 43 int main() 44 {freopen("p1487.in","r",stdin); 45 freopen("p1487.out","w",stdout); 46 scanf("%d",&n); 47 for(int i=1;i<=n;++i) 48 {scanf("%d",&num[i]); 49 cnt+=num[i]; 50 } 51 for(int i=1;i<n;++i) 52 {scanf("%d%d%d",&a,&b,&c); 53 addedge(a,b,c);//注意雙向建邊 54 addedge(b,a,c); 55 } 56 geta(1,0,0); 57 dp(1,0); 58 cout<<poi<<endl<<minn<<endl; 59 return 0; 60 }

?

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

總結(jié)

以上是生活随笔為你收集整理的动态规划：树形DP-景点中心（树的带权重心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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