設(shè)置醫(yī)院C++
題目描述
設(shè)有一棵二叉樹（如下圖），其中圈中的數(shù)字表示結(jié)點(diǎn)中居民的人口，圈邊上數(shù)字表示結(jié)點(diǎn)編號?，F(xiàn)在要求在某個(gè)結(jié)點(diǎn)上建立一個(gè)醫(yī)院，使所有居民所走的路程之和為最小，同時(shí)約定，相鄰結(jié)點(diǎn)之間的距離為1。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2×20+2×40=136=4+12+2×20+2×40=136；若醫(yī)院建在3處，則距離和=4×2+13+20+40=81=4×2+13+20+40=81……
輸入
第一行一個(gè)整數(shù)n，表示樹的結(jié)點(diǎn)數(shù)（n≤100）。接下來的n行每行描述了一個(gè)結(jié)點(diǎn)的狀況，包含三個(gè)整數(shù)，整數(shù)之間用空格（一個(gè)或多個(gè)）分隔，其中：第一個(gè)數(shù)為居民人口數(shù)；第二個(gè)數(shù)為左鏈接，為0表示無鏈接；第三個(gè)數(shù)為右鏈接，為0表示無鏈接。
輸出
一個(gè)整數(shù)，表示最小距離和。
樣例輸入?復(fù)制
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
樣例輸出?復(fù)制
81
提示
數(shù)據(jù)規(guī)模：
? 1<=N<=100 ,? 1<=w<=105
#include <bits/stdc++.h>using namespace std;const int N=105,M=2*N,INF=0x3f3f3f3f;int h[N],w[N],e[M],ne[M],idx,n;void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}int dfs(int u,int root,int dist){????int res=w[u]*dist;????for(int i=h[u];~i;i=ne[i])????{????????int j=e[i];????????if(j!=root)????????????res+=dfs(j,u,dist+1);????}????return res;}int main(){????ios::sync_with_stdio(false);????cin.tie(0);????cout.tie(0);????memset(h,-1,sizeof h);????cin>>n;????for(int i=1;i<=n;i++)????{????????int a,b,c;????????cin>>c>>a>>b;????????if(a)????????????add(i,a),add(a,i);????????if(b)????????????add(i,b),add(b,i);????????w[i]=c;????}????int res=INF;????for(int i=1;i<=n;i++)????????res=min(res,dfs(i,-1,0));????cout<<res<<endl;????return 0;}標(biāo)簽：
