论坛: 编程破解 标题: 十万火急,请大家帮帮忙!!谢谢大家了(皇宫看守问题) 复制本贴地址    
作者: 逍遥浪子 [zhousqxo]    论坛用户   登录
十万火急,请朋友们帮帮忙,马上就要交了,请能做的朋友把源程序发到我的邮箱里,先谢谢啦~~
我的油箱:zhousq00@163.com

问题描述
太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。

皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。

编程任务:
帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。

数据输入:
输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一棵树,描述如下:

第1行 n,表示树中结点的数目。

第2行至第n+1行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号i(0<i<=n),在该宫殿安置侍卫所需的经费k,该边的儿子数m,接下来m个数,分别是这个节点的m个儿子的标号r1,r2,...,rm。

对于一个n(0 < n <= 1500)个结点的树,结点标号在1到n之间,且标号不重复。


参考解答
在下面我们用根结点的标号来表示一棵树,树T就是根结点标号为T的树。

设f(T,0)表示对于一棵树T,不在T的树根上布置守卫的情况下,监控T的全部节点所需的最少的费用;
设f(T,1)表示对于一棵树T,不在T的树根上布置守卫的情况下,监控除了T的根结点以外的其他全部节点所需的最少的费用,当然也可以监控住T的根结点,不过不是强行要求的;
设f(T,2)表示对于一棵树T,在T的树根上布置守卫的情况下,监控T的全部节点所需的最少的费用;
假设T的儿子节点为T1,T2,…,Tn;则我们可以得到递归公式:

        f(T,0)=min{Σmin{f(Ti,0),f(Ti,2)+f(Tk,2)}(1)

                        f(T,1)=Σmin{f(Ti,0),f(Ti,2)}(2)

        f(T,2)=Σmin{f(Ti,0),f(Ti,1),f(Ti,2)}+ω(T)(3)

下面说明上面的三个公式的含义。

如果T的根不布置守卫,并且要求监控T的所有结点,则必须保证T的子结点中有一个结点Tk的根上布置了一个守卫,这样在Tk的根上的守卫可以同时看守T的根。至于T的其他子结点(i=1,2,..n,i≠k),可以在树根上布置守卫,也可以不布置,但是必须监控住自己所有的结点(因为T的根上没有守卫),因此选择最优的方案min{f(Ti,0),f(Ti,2)}。这样就得到了(1)式;

如果T的根不布置守卫,并且要求监控除了T的根结点以外的其他全部节点,则必须保证T的所有的子结点Ti都被监控,而不用管Ti的根上是否有守卫。于是每个子节点Ti取最优的方案min{f(Ti,0),f(Ti,2)}。这样就得到了(2)式;请注意,有可能f(T,0)=f(T,1),因为f(T,1)只是要求监控除了T的根结点以外的其他全部节点,也就是可以选择不监控T的根,而不是不允许监控T的根。当存在一个1<=k<=n,f(Tk,0)>=f(Tk,2)的时候,(2)和(1)等价,这时候f(T,1)=f(T,0);

如果规定T的根布置了守卫,则T的所有的子结点上可以布置也可以不布置守卫,而且T的所有的子结点Ti的根原来可以被监控也可以不被监控,这是因为如果原来Ti的根没有被监控,则可以被T的根上布置的那个守卫监控。因此Ti选择最优的方案min{f(Ti,0),f(Ti,1),f(Ti,2)}。这样就得到了(3)式, 这里ω(T)表示在根结点T上布置守卫的代价。实际上,在(3)中的min只要对f(Ti,1)和f(Ti,2)取min就可以了,因为根据(2)可以知道f(Ti,1)<=f(Ti,0)。

如果T是整棵树的树根的话,只要求出f(T,0),f(T,2)取较小者就是结果。

对于T没有儿子的情况(结点T为叶子),我们给出上面递归公式的边界条件:

      f(T,0)=ω(T) (4)

            f(T,1)=0(5)

        f(T,2)=ω(T)(6)

注意,这里我们做了一点特殊规定,因为根据前面对f(T,0) f(T,1) f(T,2)的定义可以知道,在T是叶子的情况下不在T的树根上布置守卫的情况下而要监控T的全部节点使不可能的,f(T,0)实际上是不存在的,但是为了使上面的公式(1)-(3)能够适用于边界条件,我们规定了(4)式对于T是叶子的情况成立。这并不影响公式(1)-(3)的正确性。(5)说明在T是叶子的情况下,不在T的树根上布置守卫的情况下并监控除了T的根结点以外的其他全部节点,最节约的办法是不布置任何的守卫,这样代价最少为0;(6)说明在T是叶子的情况下,在T的树根上布置守卫的情况下并监控T的全部节点的办法就是在节点T上布置一个守卫,代价为。

下面说说如何编程实现对于这个算法。对于这个问题,虽然可以自底向上的计算,但是不如自顶向下的计算方便。我们采用备忘录法,用一个n*3的数组记录所有的f函数。因为n<=1500;n*3不过才4500,显然不会有内存不足的问题。之所以采用自顶向下的备忘录方法,是因为输入的数据是一棵树,从树的根找到树的子结点肯定比从子节点找到父结点方便。不过也可以自底向上,这时可以用一个数组parent存储所有的节点的父结点(也就是树的父结点树组描述法),parent[i]就是结点i的父结点。这样每次要扫描一遍整个数组,太麻烦了一点。所以我们干脆选择最自然的自顶向下的计算方式。



地主 发表时间: 04-06-05 15:38

论坛: 编程破解

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写:NetDemon

粤ICP备05087286号