华为软件精英挑战赛2016题解
栏目：综合技术时间：2016-07-21 08:42:12
代码：https://github.com/jinhang/2016_Huawei_SoftWareMatch
前言
赛题源自“未来网络”业务发放中的路由计算问题。算路问题属于基础算法问题，在图论、网络、交通等各个方面均有着广泛的研究与应用，里面不乏1些经典的算法，例如最短路中的广度优先搜索，Dijkstra算法等。网络算路问题的更优算法实现对网络资源高效配置具有重要价值。
本次大赛分为初赛、复赛和总决赛3个主要阶段，当前为总决赛/复赛阶段。
总决赛/复赛赛题描写
1 问题定义
给定1个带权重的有向图G=(V,E)，V为顶点集，E为有向边集，每条有向边均有1个权重。对给定的顶点s、t，和V的子集V’和V’’，寻觅从s到t的两条不成环的有向路径P’和P’’，使得P’经过V’中所有的顶点，而P’’经过V’’中所有的顶点（对P’经过V’中顶点的顺序和P’’经过V’’中顶点的顺序不做要求）。
若不同时存在这样的两条有向路径，则输出无解，程序运行时间越短，则视为结果越优； 若同时存在这样的两条有向路径，则输出得到的两条路径，按以下优先级从高到低评价结果优劣：
1、 路径P’和P’’重合的有向边个数越少，则视为结果越优；
2、 在两条路径重合的有向边个数1样的情况下，两条路径权重总和越少，则视为结果越优；
3、 在上述两个指标1样的情况下，程序运行时间越短，则视为结果越优。
若不同时存在这样的两条有向路径，则输出无解，程序运行时间越短，则视为结果越优； 若同时存在这样的两条有向路径，则输出得到的两条路径，按以下优先级从高到低评价结果优劣：
1、 路径P’和P’’重合的有向边个数越少，则视为结果越优；
2、 在两条路径重合的有向边个数1样的情况下，两条路径权重总和越少，则视为结果越优；
3、 在上述两个指标1样的情况下，程序运行时间越短，则视为结果越优。
说明：
1）图中所有权重均为[1,100]内的整数；
2）任1有向边的出发点不等于终点；
3）连接顶点A至顶点B的有向边可能超过1条，其权重可能1样，也可能不1样；
4）该有向图的顶点不会超过2000个，每一个顶点出度（以该点为出发点的有向边的数量）不超过20；
5）V’和V’’中元素个数均不超过100，交集为空，且不包括起始顶点s和终止顶点t；
6）从s到t的不成环有向路径P是指，P为由1系列有向边组成的从s至t的有向连通路径，且不允许重复经过任1顶点；
7）路径的权重是指所有组成该路径的所有有向边的权重之和（重复边的权重应分别在两条路径中各计算1次）。
2）任1有向边的出发点不等于终点；
3）连接顶点A至顶点B的有向边可能超过1条，其权重可能1样，也可能不1样；
4）该有向图的顶点不会超过2000个，每一个顶点出度（以该点为出发点的有向边的数量）不超过20；
5）V’和V’’中元素个数均不超过100，交集为空，且不包括起始顶点s和终止顶点t；
6）从s到t的不成环有向路径P是指，P为由1系列有向边组成的从s至t的有向连通路径，且不允许重复经过任1顶点；
7）路径的权重是指所有组成该路径的所有有向边的权重之和（重复边的权重应分别在两条路径中各计算1次）。
2 输入与输出
输入文件格式
以两个.csv文件（csv是以逗号为分隔符的文本文件）给出输入数据，1个为图的数据(G)，1个为需要计算的路径信息(s,t,V’,V’’)。文件每行以换行符（ASCII’\n’即0x0a）为结尾。
1）图的数据中，每行包括以下的信息：
LinkID,SourceID,DestinationID,Cost
其中，LinkID为该有向边的索引，SourceID为该有向边的起始顶点的索引，DestinationID为该有向边的终止顶点的索引，Cost为该有向边的权重。顶点与有向边的索引均从0开始编号(不1定连续，但用例保证索引不重复)，顶点索引范围在[0，2000)，有向边索引范围在[0，40000)。
2）路径信息中，只有1行以下数据：
DemandID,SourceID,DestinationID,IncludingSet
其中，DemandID里面第1行动1，第2行动2，表示路径索引，1表示P’，2表示P’’，SourceID为起始顶点s的索引，DestinationID为终止顶点t的索引，IncludingSet表示必须经过的顶点集合V’或V’’，其中不同的顶点索引之间用“ | ”分割，如果该路径没有必经顶点要求，则此处输入NA。
1）图的数据中，每行包括以下的信息：
LinkID,SourceID,DestinationID,Cost
其中，LinkID为该有向边的索引，SourceID为该有向边的起始顶点的索引，DestinationID为该有向边的终止顶点的索引，Cost为该有向边的权重。顶点与有向边的索引均从0开始编号(不1定连续，但用例保证索引不重复)，顶点索引范围在[0，2000)，有向边索引范围在[0，40000)。
2）路径信息中，只有1行以下数据：
DemandID,SourceID,DestinationID,IncludingSet
其中，DemandID里面第1行动1，第2行动2，表示路径索引，1表示P’，2表示P’’，SourceID为起始顶点s的索引，DestinationID为终止顶点t的索引，IncludingSet表示必须经过的顶点集合V’或V’’，其中不同的顶点索引之间用“ | ”分割，如果该路径没有必经顶点要求，则此处输入NA。
输出文件格式
输出文件一样为1个.csv 文件。
1）如果该测试用例存在满足要求的有向路径P’和P’’，则输出两行信息，第1行按P’经过的有向边顺序，顺次输出有向边的索引，索引之间用“ | ”分割；第2行按P’’经过的有向边顺序顺次输出有向边的索引，索引之间用“ | ”分割；
2）如果该测试用例不同时存在两条满足要求的有向路径P’和P’’，则只输出1行信息：NA；
3）每行只允许输出最多1条有向路径，以换行符0x0a结尾。
1）如果该测试用例存在满足要求的有向路径P’和P’’，则输出两行信息，第1行按P’经过的有向边顺序，顺次输出有向边的索引，索引之间用“ | ”分割；第2行按P’’经过的有向边顺序顺次输出有向边的索引，索引之间用“ | ”分割；
2）如果该测试用例不同时存在两条满足要求的有向路径P’和P’’，则只输出1行信息：NA；
3）每行只允许输出最多1条有向路径，以换行符0x0a结尾。
3 单个用例的评分机制
有解用例的排名机制
按下面流程对参赛者结果进行排名：
Step1： 对提交的结果，进行合法性检验(详见题目描写)；
Step2： 程序运行时间不得超过10s；
若不满足上述的结果则本用例得分为0；
Step3： 路径P’和P’’重合的有向边个数（不斟酌权重）越少，排名越优；
Step4： 在路径P’和P’’重合的有向边个数1样的情况下，计算P’和P’’的权重和，权重越小，排名越优；
Step5： 在上述两个指标1样的情况下，用程序运行时间细化排名，时间越短，排名越优。
无解用例的排名机制
按以下流程对参赛者结果进行排名：
Step1： 对提交的结果，验证是不是辨认出该用例无解，若没法辨认或程序运行时间超10s，则本用例得分为0；
Step2： 用程序的运行时间进行排名，时间越短，排名越优。
单个用例的评分标准以下：
根据上面排名流程得到的排名，使用标准分计分(排名第1的提交者为100分)。
若所有人均未得到正确结果，则所有人均得分为0。
若所有人均未得到正确结果，则所有人均得分为0。
4 网站系统判分机制
复赛阶段官方网站开放接光复赛程序提交，系统平台会使用N个测试用例在线判题，参赛者对每一个测试用例都会得到1个百分制分数，使用算术平均分为该参赛者的终究得分，并展现在各区域复赛排行榜中。
特别说明：复赛阶段的在线判题评分及排行仅供参赛者参考，不纳入终究复赛成绩。
特别说明：复赛阶段的在线判题评分及排行仅供参赛者参考，不纳入终究复赛成绩。
5 简单用例说明
在如上图所示的有向图中，我们会得到下面的有向图信息：
0,0,1,1
1,1,2,1
2,2,3,1
3,1,4,1
4,4,3,1
5,0,5,1
6,5,2,1
1,1,2,1
2,2,3,1
3,1,4,1
4,4,3,1
5,0,5,1
6,5,2,1
如果此时需要寻觅从0到3的路径P’和P’’，且P’必须经过顶点1，P’’必须经过顶点2，相应的路径信息文件内容为：
1,0,3,1
2,0,3,2
2,0,3,2
对该用例，可以找到以下两组解:
0|1|2
5|6|2
和
0|3|4
5|6|2
由于第1组解两条路径的重合边个数为1，第2组解两条路径的重合边个数为0。所以此时最优解应当是0|3|4，5|6|2。
0|1|2
5|6|2
和
0|3|4
5|6|2
由于第1组解两条路径的重合边个数为1，第2组解两条路径的重合边个数为0。所以此时最优解应当是0|3|4，5|6|2。
6 复赛赛制说明
各区域升级复赛队伍为32⑶6队，复赛采取分区域现场比赛的情势展开，共分成3个小阶段：
1、 排位赛：区域现场复赛当天，各区域将通过1个官方用例对进入复赛队伍提交的程序进行判题评分并排序，排序前8名的队伍将作为下1个阶段分组赛8个小组的种子队，其余队伍通过抽签方式进行分组。
2、 分组赛：区域共分8个小组，各小组采取单循环对战方式比赛，通过积分（每场比赛胜得3分，平各得1分，负得0分）进行小组排序，排序前2名的队伍小组出线进入下1阶段的淘汰升级赛。
3、 淘汰升级赛：各小组出线队伍组成16强，分成上下半区进行两两对战淘汰升级赛，分为“1/8决赛→1/4决赛→半决赛→决赛”，最后决出区域4强进入全国总决赛。
2、 分组赛：区域共分8个小组，各小组采取单循环对战方式比赛，通过积分（每场比赛胜得3分，平各得1分，负得0分）进行小组排序，排序前2名的队伍小组出线进入下1阶段的淘汰升级赛。
3、 淘汰升级赛：各小组出线队伍组成16强，分成上下半区进行两两对战淘汰升级赛，分为“1/8决赛→1/4决赛→半决赛→决赛”，最后决出区域4强进入全国总决赛。
两队对战规则说明：
1、 复赛分组赛和淘汰升级赛均采取两队对战的情势，每场对战9局5胜。（分组赛胜积3分，负积0分，平各积1分，最后排序积分相同情况下，排位赛成绩靠前者胜出；淘汰赛出现平局，则由官方提供用例“加时赛”决出胜负）；
2、 对战双方（如红方、蓝方）各需提供2个自设计用例，官方提供5个用例，共9个用例分9局进行对战，用例发放顺序为：红方1→蓝方1→红方2→蓝方2→官方1→官方2→官方3→官方4→官方5；
3、 每局对战中，如由于己方提供用例致使自己计算不出，则该局对方自动胜出，其余根据“单个用例评分机制”判定胜负。
2、 对战双方（如红方、蓝方）各需提供2个自设计用例，官方提供5个用例，共9个用例分9局进行对战，用例发放顺序为：红方1→蓝方1→红方2→蓝方2→官方1→官方2→官方3→官方4→官方5；
3、 每局对战中，如由于己方提供用例致使自己计算不出，则该局对方自动胜出，其余根据“单个用例评分机制”判定胜负。
7 总决赛赛制说明
各区域复赛前4名共32支队伍升级总决赛，总决赛采取现场比赛的情势展开，共分成3个小阶段：
1、 排位赛：总决赛当天，组委会将通过两个官方比赛用例对进入总决赛赛队伍提交的程序进行判题评分并排序。各参赛队根据排位赛评分排名进行分档，1⑻名定为种子队（第1档），9⑴6名为第2档，17⑵4名为第3档，25⑶2名为第4档。排位赛排名仅供分组赛抽签使用，不影响参赛队伍终究排名；
2、 分组赛：全国32强共分8个小组，分组进程采取抽签进行，种子队抽签至A1-H1位置，第2档队伍抽签至A2-H2位置，第3档队伍抽签至A3-H3位置，第4档队伍抽签至A4-H4位置，构成小组赛分组。各小组采取单循环对战方式比赛，通过积分（每场比赛胜得3分，平各得1分，负得0分）进行小组排序，排序前2名的队伍小组出线进入下1阶段的淘汰升级赛。如遇积分相同情况，将根据“净胜局多-胜负关系占优-上传时间早”的优先级进行排序；
3、 淘汰升级赛：各小组出线队伍组成16强，分成上下半区进行两两对战淘汰升级赛，分为“1/8决赛→1/4决赛→半决赛→决赛”，最后决出全国总冠军。
2、 分组赛：全国32强共分8个小组，分组进程采取抽签进行，种子队抽签至A1-H1位置，第2档队伍抽签至A2-H2位置，第3档队伍抽签至A3-H3位置，第4档队伍抽签至A4-H4位置，构成小组赛分组。各小组采取单循环对战方式比赛，通过积分（每场比赛胜得3分，平各得1分，负得0分）进行小组排序，排序前2名的队伍小组出线进入下1阶段的淘汰升级赛。如遇积分相同情况，将根据“净胜局多-胜负关系占优-上传时间早”的优先级进行排序；
3、 淘汰升级赛：各小组出线队伍组成16强，分成上下半区进行两两对战淘汰升级赛，分为“1/8决赛→1/4决赛→半决赛→决赛”，最后决出全国总冠军。
两队对战规则说明：
1、 总决赛分组赛和淘汰升级赛均采取两队对战的情势，每场对战9局5胜。（分组赛允许出现平局，淘汰赛出现平局，则 “上传时间早”的队伍胜出）；
2、 对战双方（如红方、蓝方）各需提供2个自设计用例，官方提供5个用例，共9个用例分9局进行对战，用例发放顺序为：红方1→蓝方1→红方2→蓝方2→官方1→官方2→官方3→官方4→官方5；
3、 每局对战中，如由于己方提供用例致使自己计算不出，则该局对方自动胜出。官方提供用例如双方均未计算出正确路径，则双方均不得分。其余根据“单个用例评分机制”判定胜负。
2、 对战双方（如红方、蓝方）各需提供2个自设计用例，官方提供5个用例，共9个用例分9局进行对战，用例发放顺序为：红方1→蓝方1→红方2→蓝方2→官方1→官方2→官方3→官方4→官方5；
3、 每局对战中，如由于己方提供用例致使自己计算不出，则该局对方自动胜出。官方提供用例如双方均未计算出正确路径，则双方均不得分。其余根据“单个用例评分机制”判定胜负。
8 关于参赛队自行生成对战测试用例的说明
由官方在复赛阶段提供若干完全用例作为选手生成用例的素材，选手可自行编辑用例（如删增顶点、有向边、必经顶点、修改起始终止顶点等），或完全自行设计用例，只需保证用例符合题目要求且有解。官方将通过大赛网站给进入复赛的参赛队开放用例设计工具。
9 总决赛/复赛注意事项
1、 核心算法制止使用第3方代码；
2、 如参考有论文或第3方代码，必须在readme文件中提供来源说明；
3、 针对所有用例必须使用同1个算法和同1套代码实现。
2、 如参考有论文或第3方代码，必须在readme文件中提供来源说明；
3、 针对所有用例必须使用同1个算法和同1套代码实现。
初赛赛题描写
1 问题定义
给定1个带权重的有向图G=(V,E)，V为顶点集，E为有向边集，每条有向边均有1个权重。对给定的顶点s、t，和V的子集V'，寻觅从s到t的不成环有向路径P，使得P经过V'中所有的顶点(对经过V'中节点的顺序不做要求)。
若不存在这样的有向路径P，则输出无解，程序运行时间越短，则视为结果越优；若存在这样的有向路径P，则输出所得到的路径，路径的权重越小，则视为结果越优，在输前途径权重1样的条件下，程序运行时间越短，则视为结果越优。
若不存在这样的有向路径P，则输出无解，程序运行时间越短，则视为结果越优；若存在这样的有向路径P，则输出所得到的路径，路径的权重越小，则视为结果越优，在输前途径权重1样的条件下，程序运行时间越短，则视为结果越优。
说明：
1）图中所有权重均为[1，20]内的整数；
2）任1有向边的出发点不等于终点；
3）连接顶点A至顶点B的有向边可能超过1条，其权重可能1样，也可能不1样；
4）该有向图的顶点不会超过600个，每一个顶点出度(以该点为出发点的有向边的数量)不超过8；
5）V'中元素个数不超过50；
6）从s到t的不成环有向路径P是指，P为由1系列有向边组成的从s至t的有向连通路径，且不允许重复经过任1节点；
7）路径的权重是指所有组成该路径的所有有向边的权重之和。
2）任1有向边的出发点不等于终点；
3）连接顶点A至顶点B的有向边可能超过1条，其权重可能1样，也可能不1样；
4）该有向图的顶点不会超过600个，每一个顶点出度(以该点为出发点的有向边的数量)不超过8；
5）V'中元素个数不超过50；
6）从s到t的不成环有向路径P是指，P为由1系列有向边组成的从s至t的有向连通路径，且不允许重复经过任1节点；
7）路径的权重是指所有组成该路径的所有有向边的权重之和。
2 输入与输出
输入文件格式
以两个.csv 文件(csv 是以逗号为分隔符的文本文件)给出输入数据，1个为图的数据(G)，1个为需要计算的路径信息(s,t,V')。文件每行以换行符(ASCII'\n'即0x0a)为结尾。
1）图的数据中，每行包括以下的信息：
LinkID,SourceID,DestinationID,Cost
其中，LinkID 为该有向边的索引，SourceID 为该有向边的起始顶点的索引，DestinationID为该有向边的终止顶点的索引，Cost 为该有向边的权重。顶点与有向边的索引均从0 开始 编号(不1定连续，但用例保证索引不重复)。
2）路径信息中，只有1行以下数据：
SourceID,DestinationID,IncludingSet
其中，SourceID 为该路径的出发点，DestinationID 为该路径的终点，IncludingSet 表示必须经过的顶点集合V'，其中不同的顶点索引之间用'|'分割。
1）图的数据中，每行包括以下的信息：
LinkID,SourceID,DestinationID,Cost
其中，LinkID 为该有向边的索引，SourceID 为该有向边的起始顶点的索引，DestinationID为该有向边的终止顶点的索引，Cost 为该有向边的权重。顶点与有向边的索引均从0 开始 编号(不1定连续，但用例保证索引不重复)。
2）路径信息中，只有1行以下数据：
SourceID,DestinationID,IncludingSet
其中，SourceID 为该路径的出发点，DestinationID 为该路径的终点，IncludingSet 表示必须经过的顶点集合V'，其中不同的顶点索引之间用'|'分割。
输出文件格式
输出文件一样为1个.csv 文件。
1）如果该测试用例存在满足要求的有向路径P，则按P 经过的有向边顺序，顺次输出有向边的索引，索引之间用'|'分割；
2）如果该测试用例不存在满足要求的有向路径P，则输出两个字符NA；
3）只允许输出最多1条有向路径。
1）如果该测试用例存在满足要求的有向路径P，则按P 经过的有向边顺序，顺次输出有向边的索引，索引之间用'|'分割；
2）如果该测试用例不存在满足要求的有向路径P，则输出两个字符NA；
3）只允许输出最多1条有向路径。
3 单个用例的评分机制
有解用例的排名机制
按下面流程对参赛者结果进行排名：
Step1： 对提交的结果，进行合法性检验(详见题目描写)；
Step2： 程序运行时间不得超过10s；
若不满足上述的结果则本用例得分为0；
Step3： 计算提交的路径的权重，权重越小，排名越优；
Step4： 在权重相同的结果里，用程序运行时间进行排名，时间越短，排名越优。
无解用例的排名机制
按以下流程对参赛者结果进行排名：
Step1： 对提交的结果，验证是不是辨认出该用例无解，若没法辨认或算法运行时间超10s，则本用例得分为0；
Step2： 用程序的运行时间进行排名，时间越短，排名越优。
单个用例的评分标准以下：
根据上面排名流程得到的排名，使用标准分计分(排名第1的提交者为100分)。
若所有人均未得到正确结果，则所有人均得分为0。
若所有人均未得到正确结果，则所有人均得分为0。
4 终究得分机制
平台会使用N个测试用例判题，该N个测试用例分为低级、中级、高级3个等级，参赛者对每一个测试用例都会得到1个百分制分数，使用加权平均分(低级权重为0.2，中级权重为0.3，高级权重为0.5)作为该参赛者的终究得分。
特别说明：在比赛早期，平台只放出低级、中级的测试用例，故此时满分为50分，在比赛后期，才会放出高级测试用例（具体发放时间会在网站公告通知），此时满分才为100分，请各位参赛者注意。
特别说明：在比赛早期，平台只放出低级、中级的测试用例，故此时满分为50分，在比赛后期，才会放出高级测试用例（具体发放时间会在网站公告通知），此时满分才为100分，请各位参赛者注意。
5 简单用例说明
在如上图所示的有向图中，我们会得到下面的有向图信息：
0,0,1,1
1,0,2,2
2,0,3,1
3,2,1,3
4,3,1,1
5,2,3,1
6,3,2,1
1,0,2,2
2,0,3,1
3,2,1,3
4,3,1,1
5,2,3,1
6,3,2,1
如果此时需要寻觅从0到1的路径，且必须经过顶点2和3，我们会得到以下的路径信息：
0,1,2|3
对该用例，可以找到以下两条可行路径:
1|5|4
2|6|3
由于第1条路径的权重为4，第2条路径的权重为5，所以此时最优解应当1|5|4。
1|5|4
2|6|3
由于第1条路径的权重为4，第2条路径的权重为5，所以此时最优解应当1|5|4。
------分隔线----------------------------
上一篇 存储空间管理
------分隔线----------------------------