https://www.luogu.com.cn/problem/P1364
这道题是个二叉树（为什么有人要去用dfs，bfs去做？？(▔___▔））
题目描述
这道题让我们在这棵树上修建一家医院，而且让人们到医院的距离和最短，距离和也就是每一个点到医院的距离*这个点上有的人数（就这么简单）
首先我们可以建一个结构体，里面存了每一个点的信息：人数，左子树，右子树，根节点，到医院的距离。
struct node{ ll shu,zuo,you,gen,ju;//人数，左子树，右子树，根节点，距离 }a[110];
照着输入，可是问题来了，它的根节点怎么求？
很简单，就是把它的左子树还有右子树的根节点标记为i，就解决了。
for(int i=1;i<=n;i++){ cin>>a[i].shu>>a[i].zuo>>a[i].you;//人数，左子树，右子树 a[a[i].zuo].gen=i;//标记 a[a[i].you].gen=i; }
后面开一个for，枚举如果第i个点就是医院，算出他的距离和，再取最小值
那每一个点到医院的距离怎么求？
可以写个函数计算，代码如下：
void juli(ll k,ll h){//这个点，它的距离，初始值就是i和0 a[k].ju=h;//把距离赋值 vis[k]=1;//标记，不然有的点有可能重复计算 if(a[k].zuo!=0&&vis[a[k].zuo]==0) juli(a[k].zuo,h+1);//左子树不 为空并且他没有被标记过，进左子树，距离+1 if(a[k].you!=0&&vis[a[k].you]==0) juli(a[k].you,h+1);//右子树不为空并且他没有被标记过，进右子树，距离+1 if(a[k].gen!=0&&vis[a[k].gen]==0) juli(a[k].gen,h+1);//根节点不为空并且他没有被标记过，进根节点，距离+1 return ;//返回 }
注：每一次vis数组都要清0
计算距离和不用说：
for(int j=1;j<=n;j++) sum+=a[j].ju*a[j].shu;//距离*人数
最后再取一个最小值，输出答案，就可以了
附上代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node{ ll shu,zuo,you,gen,ju; }a[110]; ll vis[110],n,ans=0x3f3f3f3f; void juli(ll k,ll h){ a[k].ju=h; vis[k]=1; if(a[k].zuo!=0&&vis[a[k].zuo]==0) juli(a[k].zuo,h+1); if(a[k].you!=0&&vis[a[k].you]==0) juli(a[k].you,h+1); if(a[k].gen!=0&&vis[a[k].gen]==0) juli(a[k].gen,h+1); return ; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].shu>>a[i].zuo>>a[i].you; a[a[i].zuo].gen=i; a[a[i].you].gen=i; } for(int i=1;i<=n;i++){ //假设a[i]为医院 memset(vis,0,sizeof(vis)); juli(i,0); ll sum=0; for(int j=1;j<=n;j++) sum+=a[j].ju*a[j].shu; ans=min(ans,sum); }cout<<ans; return 0; }