1.4 秦始皇陵（难度：★★★★☆）
1.4.1 试题
题目描述
《史记•秦始皇本纪》载：“始皇初即位，穿治郦山，及并天下，天下徒送诣七十馀万人，穿三泉，下铜而致椁，宫观百官奇器珍怪徙臧满之。令匠作机弩矢，有所穿近者辄射之。以水银为百川江河大海，机相灌输，上具天文，下具地理。以人鱼膏为烛，度不灭者久之。”
公元20××年12月17日，一支来自南粤的考察队GDKOI在领队Prof. Guo的带领下对骊山周边古迹进行考察时，一块色泽古朴的石板吸引了考察队的注意。掀开石板以后，眼前的景象让所有在场的队员震惊了！这是一个庞大的地下库藏，数百个井然有序的书架上，摆放了一卷卷的竹简。考察队中的文史杂家小熊经过三天三夜不眠不休的浏览分析，初步确定，这是秦皇陵地宫工程建设文档库！
这一重大发现，不仅是辉煌的中华古文明的写照，也证明了中国古代就已有完善的工程体系理念，使秦皇古陵再次聚集了全世界的焦点！
GDKOI考察队继续他们对书库的整理工作，我们的故事也由此展开。
小熊在整理的过程中，被一列标注为《互知经注》的文档吸引住。原来当时通信手段落后，如此庞大的工程为实现消息的高效传输，秦皇陵的工程师们开发出一套有效的消息传输方案！经过审阅翻译，小熊得出如下信息。
整个工程有P0…Pn−1共n个通信员，消息最初从P0处发出，然后经过相互转发，当所有通信员收到消息以后，发布工作完成。消息具体发布的过程是这样的：
开始只有P0知道消息，而其他通信员均不知道消息。P0在n−1个尚未获知消息的通信员中选择一个Px，将消息转发给Px，这样知道消息的有P0与Px，该过程完成后他们立即继续在尚未获知消息的通信员中各自选择一个来转发消息。注意每次每人只能转发给一个通信员，并且每次转发的过程都需要耗费一定的时间。获知消息的通信员越来越多，他们也各自分别去转告其余尚未获知消息的通信员，直到所有通信员皆获知消息，消息发布完成。
当然，智慧的秦代人不是简单机械地执行这种工作。他们的运作有以下三条重要规则：
（1）耗时。不同的两个通信员之间的消息转告需要耗费不同的时间。
（2）有限工作量。对于每个通信员Pi，都有一个工作量的上限Ci。当通信员Pi获知消息以后，他最多只能向Ci个其他通信员转发消息。
（3）传送深度约束。传送深度是指任意一个通信员收到消息时，该消息从P0发出经过发送及转发的次数。若Px从P0处收到消息，则至Px的传送深度为1；Py再从Px处收到经Px转发的消息，则至Py的传送深度为2，依此类推。而对于全体通信员都有一个传送深度上限D，即消息达至任意一个通信员的传送深度都不能大于D。
现在，小熊整理出了秦皇陵工程的数据，他想知道，一个消息最少需要多少时间才能发布完毕（即最少需要多少时间才能令所有通信员获知）？
输入格式
输入文件包含多组数据。
每组数据第1行是整数n（1≤n≤15），表示有P 0…Pn−1共n个通信员。消息最初从P0开始发布。
接下来n行：每行n个整数。标号从0开始到n−1，第i行j列的值Tij是通信员i把消息告知j所需的时间。Tij = Tiji恒成立。
第n+3行：n个整数C0…Cn−1，表示P0至Pn−1的工作量上限。
第n+4行：一个整数D，为传送深度上限。
输入文件读入至文件末（EOF）结束。
输出格式
对于每组数据，输出一个正整数。若消息不能成功发布至所有通信员则输出−1，否则输出发布成功所需的最少时间。
输入样例1
4
0 1 8 3
1 0 2 7
8 2 0 9
3 7 9 0
2 2 2 2
3
输出样例1
4
输入样例2
4
0 1 8 3
1 0 2 7
8 2 0 9
3 7 9 0
1 2 2 2
3
输出样例2
10
输入样例3
4
0 3 2 1
3 0 1 2
2 1 0 2
1 2 2 0
2 2 2 2
1
输出样例3
-1
样例注释
样例1：P0先发给P1耗时1；P0发给P3的同时P1发给P2，分别耗时3和2；一共需要耗时4。
样例2：P0先发给P1耗时1；因为P0最多只能转发一次，所以P0不能再发送；然后P1相继转发给P2和P3，分别耗时2和7；一共需要耗时10。
样例3：因为受到有限工作量和传送深度的限制，至少有一人始终不能获知消息，故输出−1。
1.4.2 题目分析和算法实现
本题的基础模型是最优组播树，属于NP问题，只能采用搜索算法。
最简单的搜索办法是：开始把P0标号，P1～Pn−1都未标号。每次枚举一个未标号的点和一个已标号的点，建立一条边。同时考虑树的深度不能超过D，以及每个点的转发限制就可以搜出结果。
这样的搜索办法非常清晰简洁，但耗时非常多！考虑搜索每一层需要选择一个已标号和一个未标号的点，需要选择n−1次才能构造出这棵组播树，最坏算法复杂度为O（n2n）。由于这个问题能归约到一个已存在的一个NP问题上，因此可以放弃考虑任何多项式的算法，转而考虑如何能增加搜索速度。经过观察上述朴素的搜索算法，发现可以出现这样的情况：
若某一状态，先枚举了已标号的Px和未标号的Py连上一条边，搜索至下一层时，枚举了已标号的Px+1和未标号的Py+1连上边。回溯以后，又枚举了一次Px+1和Py+1，然后深入至下一层递归时枚举了Px和Py连边，则出现了多余的搜索状态。这种冗余的累积会大大降低搜索效率。
因此我们从问题出发，可以设计出一个更高效的搜索算法：把已经加入树的点标上序号，依据序号从小到大的顺序枚举该节点的儿子节点。在递归的每一层，枚举了一个节点指定节点的儿子节点以后，深入至下一层时要么枚举下一个该指定节点的儿子节点，要么推移至序号加1的指定节点寻找儿子节点。
再分析这种搜索方法，每一层的搜索量只有朴素算法的一半（想想为什么），复杂度降为O（n/2）2n。理论复杂度虽然还是接近的，但是实际效率已经相差4n倍了，是一种巨大的提升。在面对这类搜索问题时，往往需要从大处着手，换一个角度思考，就能够找到更加高效的方法。
1.4.3 参考程序及程序分析
#include ＜stdio.h＞ #include ＜string.h＞ #define MaxN 15 //最大通信员数量 long n, g[MaxN + 1][MaxN + 1], c[MaxN + 1], d; //通信员数量n，转发耗时矩阵g，工作量上限c，传送深度d long mark[MaxN + 1], s[MaxN + 1], last[MaxN + 1], ans; long a[MaxN + 1], tot; //搜索的每一层的选择和当前搜索层数 void dfs(long x, long max) //第Px个通信员，当前最多所需的时间 { long i, temp; if (tot == n) { //叶子节点 //求出所有节点的最大花费temp temp = s[0]; for (i = 0; i ＜ n; i++) if (s[i] ＞ temp) temp = s[i]; if (ans == -1 || temp ＜ ans) ans = temp; //保存最优解 return; } if (ans != -1 && max ＞ ans) return; //可行性剪枝 if (x ＜ tot -1) dfs(x + 1, max); //枚举Px+1节点 for (i = 1; i ＜ n; i++) if (s[i] == -1 && c[a[x]] ＞ 0 && mark[a[x]] + 1 ＜= d) { mark[i] = mark[a[x]] + 1; //传送深度 a[tot++] = i; //a数组记录搜索节点的顺序 c[a[x]]--; //Px的剩余工作量 s[a[x]] += g[a[x]][i]; //a[x]与i间传送的耗时 s[i] = s[a[x]]; if (s[i] ＞ max) dfs(x, s[i]); //继续枚举Px节点 else dfs(x, max); s[i] = -1; //参数回滚 s[a[x]] -= g[a[x]][i]; c[a[x]]++; tot--; } } void main() { long i, j; freopen("qin.in", "r", stdin); //输入文件 freopen("qin.out", "w", stdout); //输出文件 while (scanf("%ld", &n) != EOF) { //读入通信员数量至文件结束 for (i = 0; i ＜ n; i++) for (j = 0; j ＜ n; j++) scanf("%ld", &g[i][j]); //读入耗时矩阵 for (i = 0; i ＜ n; i++) scanf("%ld", &c[i]); //读入工作量上限 scanf("%ld", &d); //读入传送深度 j = 0; for (i = 0; i ＜ n; i++) j += c[i]; //求通信员总工作量 if (j ＜ n -1) { //如果总工作量小于边数，则不可能构成一棵树 printf("-1\n"); //输出无解 continue; } memset(s, -1, sizeof(s)); //初始化 memset(last, -1, sizeof(last)); mark[0] = a[0] = s[0] = 0; tot = 1; ans = -1; dfs(0, 0); //递归求解答案 printf("%ld\n", ans); } fclose(stdout); }
1.4.4 部分测试数据和输出结果
测试数据
4
0 1 8 3
1 0 2 7
8 2 0 9
3 7 9 0
2 2 2 2
3
4
0 1 8 3
1 0 2 7
8 2 0 9
3 7 9 0
1 2 2 2
3
4
0 3 2 1
3 0 1 2
2 1 0 2
1 2 2 0
2 2 2 2
1
1
0
0
5
0 94 13 9100
94 0 70 75 45
13 70 0 79 88
9 75 79 0 21
100 45 88 21 0
2 4 4 1 2
3
4
0 55 4 47
55 0 52 99
4 52 0 90
47 99 90 0
0 2 1 2
3
输出结果
4
10
-1
0
75
-1