【通讯传递】

【题目描述】

据史书记载,秦朝时期的通信手段比较落后,为实现消息的高效传输,秦朝的工程师们开发出一套有效的消息传输方案!

有P0~Pn-1共n个通信员,消息最初从P0处发出,然后经过相互转发,当所有通信员受到消息以后,发布工作完成。消息具体发布的过程是这样的:

开始只有P0知道消息而其他通信员均不知道消息。P0在n-1个尚未获知消息的通信员中选择一个Px,将消息转发给Px,这样知道消息的有P0和Px,该过程完成后他们立即继续在尚未获知消息的通信员中各自选择一个来转发消息。注意每次每人只能转发给一个通信员,并且每次转发的过程都需要耗费一定的时间,获知消息的通信员越来越多,他们也各自分别去转告其余尚未获知消息的通信员,直到所有通信员皆获知消息,消息发布完成。

当然,智慧的秦代人不是简单机械地执行这种工作,他们的运作有以下三条重要规则:

①耗时。不同的两个通信员之间的消息转告需要耗费不同的时间。

②有限工作量。对于每个通信员Pi,都有一个工作量的上限Ci,当通信员P1获知消息以后,他最多只能向Ci个其他通信员转发消息。

③传送深度约束。传送深度是指任意一个通信员收到消息时,该消息从P0发出经过发送及转发的次数。若Px从P0处收到消息,则至Px的传送深度为1,Py再从Px处收到经Px转发的消息,则至Py的传送深度为2,依次类推。而对于全体通信员都有一个传送深度上限D,即消息到达任意一个通信员的传送深度都不能大于D。

现在,小YJQ整理除了相关数据,他想知道,一个消息最少需要多少时间才能发布完毕(即最少需要多少时间才能令所有通信员获知)?

【输入格式】

输入文件包含多组数据。

每组数据的第一行是整数n(n≤15),表示共有P0~Pn-1共n个通信员。消息最初从P0开始发布。

接下来n行:每行n个整数。标号从0开始到n-1,第i行j列的值Tij是通信员o把消息告知j所需的时间。Tij=Tji恒成立。

第n+3行:n个整数C0~Cn-1,表示P0~Pn-1的工作量上限。

第n+4行:一个整数D,为传送深度上限。

【输出格式】

对于每组数据,输出一个正整数。若消息不能成功发布至所有通信员则输出-1,否则输出发布成功所需的最少时间。

【输入样例】

4

0 1 8 3

1 0 2 7

8 2 0 9

3 7 9 0

2 2 2 2

3

【输出样例】

10

【数据规模】

对于50%的数据:1≤n≤6

对于100%的数据:1≤n≤15

本题的基础模型是最优组播树,属于NP问题,只能采用搜索算法。

最简单的搜索办法是:开始把P0标号,P1~Pn-1都未标号,每次枚举一个未标号的点和一个已标号的点,建立一条边。同时考虑树的深度不能超过D,以及每个点的转发限制就可以搜出结果。

然而,时间复杂度n^(2n)直接爆炸只能过50分。

100分的迷之DFS:

把已经加入树的点标上序号,依据序号从小到大的顺序枚举该节点的儿子节点。在递归的每一层,枚举了一个节点指定节点的儿子节点以后,深入至下一层时要么枚举下一个该指定节点的儿子节点,要么推移至序号加一的指定节点寻找儿子节点。时间复杂度(n/2)^(2n)能AC此题。

总之,在面对这类搜索问题时,往往需要从大处着手,换一个角度思考,就能找到能加高效的方法。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*