时间限制: 1000 ms 内存限制: 65536 KB提交数: 9160 通过数: 6342

【题目描述】

设有一棵二叉树(如下图),其中圈中的数字表示结点中居民的人口,圈边上数字表示结点编号。现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,相邻结点之间的距离为1。就本图而言,若医院建在1处,则距离和=4+12+2×20+2×40=136;若医院建在3处,则距离和=4×2+13+20+40=81……

【输入】

第一行一个整数n,表示树的结点数(n100)。接下来的n行每行描述了一个结点的状况,包含三个整数,整数之间用空格(一个或多个)分隔,其中:第一个数为居民人口数;第二个数为左链接,为0表示无链接;第三个数为右链接,为0表示无链接。

【输出】

一个整数,表示最小距离和。

【输入样例】

5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0

【输出样例】

81

算法分析

这是一道简单的二叉树应用问题,问题中的节点数并不多,数据规模也不大,采用邻接矩阵存储,用Floyed求出任意两节点之间的最短路径,然后穷举医院可能建立的n个节点位置找出一个最小距离的位置即可。

当然也可以用双链表结构或带父节点信息的数组存储结构来解决,但实际操作稍微麻烦了一点。

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int a[101];
int g[101][101];
int main ()
{
	int n,i,j,k,l,r,min,total;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			g[i][j]=1000000;
		}
	}
	for(i=1;i<=n;i++)
	{
		g[i][j]=0;
		cin>>a[i]>>l>>r;
		if(l>0) g[i][l]=g[l][i]=1;
		if(r>0) g[i][r]=g[r][i]=1;
	}
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
		{
			if(i!=k)
			{
				for(j=1;j<=n;j++)
				{
					if(i!=j&&k!=j&&g[i][k]+g[k][j]<g[i][j])
					{
						g[i][j]=g[i][k]+g[k][j];
					}
				}
			}
		}
	}
	min=0x7fffffff;
	for(i=1;i<=n;i++)
	{
		total=0;
		for(j=1;j<=n;j++)
		{
			total+=g[i][j]*a[i];
		}
		if(total<min) min=total;
	}
	cout<<min<<endl;
	return 0;
}

4 条评论

  • @ 1 年前
    #include<bits/stdc++.h>
    using namespace std;
    int n,t,i,j,k;
    int a[101];
    int g[101][101];
    int main(){
    	int n,i,j,k,l,r,min,total;
    	cin>>n;
    	for(i=1;i<=n;i++)
    		for(j=1;j<=n;j++)
    			g[i][j]=1000000;
    	for(i=1;i<=n;i++){
    		g[i][i]=0;
    		cin>>a[i]>>l>>r;
    		if(l>0)g[i][l]=g[l][i]=1;
    		if(r>0)g[i][r]=g[r][i]=1;
    	}
    	for(k=1;k<=n;k++)
    		for(i=1;i<=n;i++)
    		if(i!=k)
    			for(j=1;j<=n;j++)
    			if(i!=j&&k!=j&&g[i][k]+g[k][i]<g[i][j])	g[i][j]=g[i][k]+g[k][j];
    	min=0x7fffffff;
    	for(i=1;i<=n;i++){
    		total=0;
    		for(j=1;j<=n;j++)total+=g[i][j]*a[j];
    		if(total<min)min=total;
    	}
    	cout<<min<<endl;
    	return 0;
    }
    
    • @ 1 年前
      已修改
      c++
      #include<bits/stdc++.h>
      using namespace std;
      int n,t,i,j,k;
      int a[101];
      int g[101][101];
      int main(){
      	int n,i,j,k,l,r,min,total;
      	cin>>n;
      	for(i=1;i<=n;i++)
      		for(j=1;j<=n;j++)
      			g[i][j]=1000000;
      	for(i=1;i<=n;i++){
      		g[i][i]=0;
      		cin>>a[i]>>l>>r;
      		if(l>0)g[i][l]=g[l][i]=1;
      		if(r>0)g[i][r]=g[r][i]=1;
      	}
      	for(k=1;k<=n;k++)
      		for(i=1;i<=n;i++)
      		if(i!=k)
      			for(j=1;j<=n;j++)
      			if(i!=j&&k!=j&&g[i][k]+g[k][i]<g[i][j])	g[i][j]=g[i][k]+g[k][j];
      	min=0x7fffffff;
      	for(i=1;i<=n;i++){
      		total=0;
      		for(j=1;j<=n;j++)total+=g[i][j]*a[j];
      		if(total<min)min=total;
      	}
      	cout<<min<<endl;
      	return 0;
      }
      
      • @ 1 年前
        已修改
        #include
        using namespace std;
        int n,t,i,j,k;
        int a[101];
        int g[101][101];
        int main(){
        cin>>n;
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        g[i][j]=1000000;
        for(i=1;i<=n;i++){
        g[i][i]=0;
        cin>>a[i]>>l>>r;
        if(l>0)g[i][l]=g[l][i]=1;
        if(r>0)g[i][r]=g[r][i]=1;
        }
        for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
        if(i!=k)
        for(j=1;j<=n;j++)
        if(i!=j&&k!=j&&g[i][k]+g[k][i]<g[i][j])g[i][j]=g[i][k]+g[k][j];
        min=0x7fffffff;
        for(i=1;i<=n;i++){
        total=0;
        for(j=1;j<=n;j++)total+=g[i][j]*a[j];
        if(total<min)min=total;
        }
        cout<<min<<endl;
        return 0;
        }
        
        • @ 1 年前
          已修改
          using namespace std;
          int n,t,i,j,k;
          int a[101];
          int g[101][101];
          int main(){
          int n,i,j,k,l,r,min,total;
          cin>>n;
          for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
          g[i][j]=1000000;
          for(i=1;i<=n;i++){
          g[i][i]=0;
          cin>>a[i]>>l>>r;
          if(l>0)g[i][l]=g[l][i]=1;
          if(r>0)g[i][r]=g[r][i]=1;
          }
          for(k=1;k<=n;k++)
          for(i=1;i<=n;i++)
          if(i!=k)
          for(j=1;j<=n;j++)
          if(i!=j&&k!=j&&g[i][k]+g[k][i]<g[i][j])	g[i][j]=g[i][k]+g[k][j];
          min=0x7fffffff;
          for(i=1;i<=n;i++){
          total=0;
          for(j=1;j<=n;j++)total+=g[i][j]*a[j];
          if(total<min)min=total;
          }
          cout<<min<<endl;
          return 0;
          }
          
          • 1