SGOI13之《粮仓》解题报告
   
　　题目大意：
　　题目给出了一棵树，要求在树的一个结点处建一个粮仓，使得将所有结点的粮食运到粮仓的费用最少。

　　问题分析：
　　由于数据量大，如果使用原始的算法求出任意两点的最短路显然是不行的。所以我们来考虑作为一棵树，是否有特殊的办法。因为是一棵树，所以任意两个结点有且只有一条唯一的通路。我们先假设已经知道粮仓只能建在a或b点，且a,b相邻。于是要将在a一边的粮食运到b一定要经过a；同样，要将在b一边的粮食运到a也一定要经过b。如图：
　　　　　　　　


　　这样我们就可以将1，2的粮食先运到a，3，4的粮食x先运到b；无论粮仓建在a或b，这个过程是一定少不了的。所以这个过程的费用无需计算。在把粮食运到两点后问题就简单了。我只要比较a,b两点，谁的粮食多粮仓就应该建在哪一点上。

　　算法实现：
　　有了上述的想法，不难发现粮仓的位置与路程无关，，只和每个结点粮食产量有关。我们先建设将粮仓建在树的根结点，然后将其与自己的子结点对比，判断将粮仓移到子结点是否更优，判断方法如上所述。如果更优就将粮仓移至其子结点。重复这一过程，知道粮仓无法移动为止。

　　参考程序：

　　
　　
　　
　　


    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有