《2016华为网络技术大赛试题及解答》由会员分享，可在线阅读，更多相关《2016华为网络技术大赛试题及解答（6页珍藏版）》请在金锄头文库上搜索。
1、赛题源自“未来网络”业务发放中的路由计算问题。算路问题属于基础算法 问题，在图论、网络、交通等各个方面均有着广泛的研究与运用，里面不 乏一些经典的算法，例如最短路中的广度优先搜索，Dijkstra算法等。网 络算路问题的更优算法实现对于网络资源高效配置具有重要价值。1问题定义给定一个带权重的有向图G=（V,E），V为顶点集，E为有向边集，每一条 有向边均有一个权重。对于给定的顶点s、t，以及V的子集V，寻找从s 到t的不成环有向路径P，使得P经过V中所有的顶点（对经过V中节点 的顺序不做要求）。若不存在这样的有向路径P，则输出无解，程序运行时间越短，则视为结 果越优；若存在这样的有向路径P，则
2、输出所得到的路径，路径的权重越 小，则视为结果越优，在输出路径权重一样的前提下，程序运行时间越短, 则视为结果越优。说明：1）图中所有权重均为1，20内的整数；个人吐槽：没有复汉值经典Dijkstr算法可能适用2）任一有向边的起点不等于终点；个人吐槽：极端情况被踢出，减难度3）连接顶点A至顶点B的有向边可能超过一条，其权重可能一样，也可 能不一样；个人吐槽：不一样就取较小者4）该有向图的顶点不会超过600个，每个顶点出度（以该点为起点的有向 边的数量）不超过8 ；5）V中元素个数不超过50 ；个人吐槽：指定点集越多，耗越夸张，难点之一，优化点之一。6）从s到t的不成环有向路径P是指，P为由一系
3、列有向边组成的从s至t的有向连通路径，且不允许重复经过任一节点；7）路径的权重是指所有组成该路径的所有有向边的权重之和。2输入与输出输入文件格式以两个.csv文件（csv是以逗号为分隔符的文本文件）给出输入数据，一个 为图的数据（G），一个为需要计算的路径信息（s,t,V）。文件每行以换行符 （ASCIIn即 0x0a）为结尾。1）图的数据中，每一行包含如下的信息：LinkID,SourceID,DestinationID,Cost其中，LinkID为该有向边的索引，SourceID为该有向边的起始顶点的索 弓I，DestinationID为该有向边的终止顶点的索引，Cost为该有向边的权重。
4、 顶点与有向边的索引均从0开始编号（不一定连续，但用例保证索引不重 复）。2）路径信息中，只有一行如下数据：SourceID,DestinationID,IncludingSet其中，SourceID为该路径的起点，DestinationID为该路径的终点， IncludingSet表示必须经过的顶点集合V，其中不同的顶点索引之间用T 分割。输出文件格式输出文件同样为一个.csv文件。1）如果该测试用例存在满足要求的有向路径P，则按P经过的有向边顺 序，依次输出有向边的索引，索引之间用|分割；2）如果该测试用例不存在满足要求的有向路径P，则输出两个字符NA ;3）只允许输出最多一条有向路径。3
5、单个用例的评分机制有解用例的排名机制按下面流程对参赛者结果进行排名：Stepl :对于提交的结果，进行合法性检验（详见题目描述）；Step2 :程序运行时间不得超过10s ；若不满足上述的结果则本用例得分为0 ；Step3 :计算提交的路径的权重，权重越小，排名越优；Step4 :在权重相同的结果里，用程序运行时间进行排名，时间越短，排 名越优。无解用例的排名机制按下列流程对参赛者结果进行排名：Stepl :对于提交的结果，验证是否识别出该用例无解，若无法识别或者 算法运行时间超10s，则本用例得分为0 ；Step2 :用程序的运行时间进行排名，时间越短，排名越优。单个用例的评分标准如下：根据
6、上面排名流程得到的排名，使用标准分计分（排名第一的提交者为100 分）。若所有人均未得到正确结果，则所有人均得分为0。4最终得分机制平台会使用N个测试用例判题，该N个测试用例分为初级、中级、高级 三个等级，参赛者对于每个测试用例都会得到一个百分制分数，使用加权 平均分（初级权重为0.2，中级权重为0.3,高级权重为0.5）作为该参赛者 的最终得分。特别说明：在比赛初期，平台只放出初级、中级的测试用例，故此时满分 为50分，在比赛后期，才会放出高级测试用例（具体发放时间会在网站 公告通知），此时满分才为100分，请各位参赛者注意。5简单用例说明在如上图所示的有向图中，我们会得到下面的有向图信息：
7、/ * 苴为 LinkSDrCostS.11,0,2,2 2,0,3,1 3,2,1,34,3,1,15,2,3,16,3,2,1如果此时需要寻找从0到1的路径，且必须经过顶点2和3,我们会得到 如下的路径信息：0,1,213对于该用例，可以找到如下两条可行路径:11514 21613由于第一条路径的权重为4，第二条路径的权重为5，所以此时最优解应 该 11514。运行环境CPU : Intel Xeon CPU E5-2690 V2 3.00GHz内存：2G内核：单核编译器：gcc 4.8.4 ; java 1.7.0_95 ;操作系统：linux Ubuntu 14.04.3 LTS，内核版本 Linux version 3.13.0-24-ginericSDK :为方便选手做题，分别提供c+（兼容c）和JavaSDK包供参考 （见赛题下载包），详细描述信息请见SDK目录下的readme.txt。
