题意

乐,应该题目能看懂吧,乐

求所有人都到医院的最少步数

思路

BFS二叉树

有一点要​注意​,BFS记得要搜索父节点哦(三叉树,呵呵)

代码(密,长)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=114514;
int n,mi=114514;
struct node
{
	int f,p,fa,l,r;
/*
f:到医院的步数
p:人数
fa:父节点
l:左儿子
r:右儿子
*/
};
node g[N];//二叉树
bool vis[N];//标记数组
int main()
{
	cin>>n;//输入
	for(int i=0;i<n;i++)
	{
		int p,l,r;
		cin>>p>>l>>r;//人数,左儿子,右儿子
		g[i+1].p=p;
		g[i+1].l=l;
		g[i+1].r=r;
		g[l].fa=i+1;//注意,要记录父节点
		g[r].fa=i+1;
	}
	int sum;
	for(int i=1;i<=n;i++)
	{
		sum=0;
		fill(vis,vis+N,0);//重置标记
		for(int j=0;j<N;j++)//重置步数
		{
			g[j].f=0;
		}
		queue<int >q;
		q.push(i);
		vis[i]=1;
		while(q.size())//BFS
		{
			g[q.front()].f++;//步数
			if(g[q.front()].l!=0 && !vis[g[q.front()].l])//左儿子
			{
				q.push(g[q.front()].l);
				vis[g[q.front()].l]=1;
				g[g[q.front()].l].f=g[q.front()].f;//设置为父节点+1的步数
			}
			if(g[q.front()].r!=0 && !vis[g[q.front()].r])//右儿子
			{
				q.push(g[q.front()].r);
				vis[g[q.front()].r]=1;
				g[g[q.front()].r].f=g[q.front()].f;//设置为父节点+1的步数
			}
			if(g[q.front()].fa!=0 && !vis[g[q.front()].fa])//父节点(这个要注意的,必须有)
			{
				q.push(g[q.front()].fa);
				vis[g[q.front()].fa]=1;
				g[g[q.front()].fa].f=g[q.front()].f;//设置为父节点+1的步数
			}
			sum+=g[q.front()].p*(g[q.front()].f-1);//统计每个居民走的步数
			q.pop();//这里要记得
		}
		mi=min(mi,sum);//取最小值
	}
	cout<<mi;//输出
	return 0;//完结散花
}

题意

在二叉树中，在一个点设一个医院，让其他点到医院的距离的和^[1]最小

思路

还好是二叉树，如果是图，那就g了

先枚举医院在的节点，把和对比，找最小值

代码

#include <bits/stdc++.h>
using namespace std;
struct tree{
	int i,n,l,r,f;	// i 为索引，n 为人数，l 为左子树，r 为右子树，f 为父亲
	int ceng;	// 离医院的距离
}a[105];
int mn = 113506;	// 猜猜为什么是这个数
bool f[105];
int bfs(int n){
	int sum = 0;
	queue<tree> q;
	q.push(a[n]);
	f[n] = 1;
	while(!q.empty()){
		tree x = q.front();
		sum += x.ceng * x.n;
		if(x.f && !f[x.f]){	// 父节点
			q.push({x.f,a[x.f].n,a[x.f].l,a[x.f].r,a[x.f].f,x.ceng + 1});
			f[x.f] = 1;
		}
		if(x.l && !f[x.l]){	// 左子树
			q.push({x.l,a[x.l].n,a[x.l].l,a[x.l].r,a[x.l].f,x.ceng + 1});
			f[x.l] = 1;
		}
		if(x.r && !f[x.r]){	// 右子树
			q.push({x.r,a[x.r].n,a[x.r].l,a[x.r].r,a[x.r].f,x.ceng + 1});
			f[x.r] = 1;
		}
//		printf("%d: %d %d %d %d %d\n",x.i,cnt,x.f,x.l,x.r,x.ceng);
		q.pop();
	}
	return sum;
}
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		int w,u,v;
		cin >> w >> u >> v;
		a[i].i = i;
		a[i].n = w,a[i].l = u,a[i].r = v;	// 设置人数、左子树、右子树
		a[u].f = i,a[v].f = i;	// 设置左子树、右子树的父节点
	}
	for (int i = 1;i <= n;i++){
		memset(f,0,sizeof(f));	// 重置标记数组
		mn = min(bfs(i),mn);
//		printf("%d\n",mn);
	}
	cout << mn;
	return 0;
}