您當前位置：首頁 > php開源 > 綜合技術 > 華為軟件精英挑戰賽2016題解

華為軟件精英挑戰賽2016題解

來源：程序員人生發布時間：2016-07-21 08:42:12 閱讀次數：3449次

代碼：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）圖中所有權重均為[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 輸入與輸出

輸入文件格式

以兩個.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個.csv 文件。
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。

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

如果此時需要尋覓從0到3的路徑P’和P’’，且P’必須經過頂點1，P’’必須經過頂點2，相應的路徑信息文件內容為：

1,0,3,1
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。

6 復賽賽制說明

各區域升級復賽隊伍為32⑶6隊，復賽采取分區域現場比賽的情勢展開，共分成3個小階段：

1、排位賽：區域現場復賽當天，各區域將通過1個官方用例對進入復賽隊伍提交的程序進行判題評分并排序，排序前8名的隊伍將作為下1個階段分組賽8個小組的種子隊，其余隊伍通過抽簽方式進行分組。
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、每局對戰中，如由于己方提供用例致使自己計算不出，則該局對方自動勝出，其余根據“單個用例評分機制”判定勝負。

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決賽→半決賽→決賽”，最后決出全國總冠軍。

兩隊對戰規則說明：

1、總決賽分組賽和淘汰升級賽均采取兩隊對戰的情勢，每場對戰9局5勝。（分組賽允許出現平局，淘汰賽出現平局，則 “上傳時間早”的隊伍勝出）；
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套代碼實現。

初賽賽題描寫

1 問題定義

給定1個帶權重的有向圖G=(V,E)，V為頂點集，E為有向邊集，每條有向邊均有1個權重。對給定的頂點s、t，和V的子集V'，尋覓從s到t的不成環有向路徑P，使得P經過V'中所有的頂點(對經過V'中節點的順序不做要求)。
若不存在這樣的有向路徑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 輸入與輸出

輸入文件格式

以兩個.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個.csv 文件。
1）如果該測試用例存在滿足要求的有向路徑P，則按P 經過的有向邊順序，順次輸出有向邊的索引，索引之間用'|'分割；
2）如果該測試用例不存在滿足要求的有向路徑P，則輸出兩個字符NA；
3）只允許輸出最多1條有向路徑。

3 單個用例的評分機制

有解用例的排名機制

按下面流程對參賽者結果進行排名：

Step1：對提交的結果，進行合法性檢驗(詳見題目描寫)；

Step2：程序運行時間不得超過10s；

若不滿足上述的結果則本用例得分為0；

Step3：計算提交的路徑的權重，權重越小，排名越優；

Step4：在權重相同的結果里，用程序運行時間進行排名，時間越短，排名越優。

無解用例的排名機制

按以下流程對參賽者結果進行排名：

Step1：對提交的結果，驗證是不是辨認出該用例無解，若沒法辨認或算法運行時間超10s，則本用例得分為0；

Step2：用程序的運行時間進行排名，時間越短，排名越優。

單個用例的評分標準以下：

根據上面排名流程得到的排名，使用標準分計分(排名第1的提交者為100分)。
若所有人均未得到正確結果，則所有人均得分為0。

4 終究得分機制

平臺會使用N個測試用例判題，該N個測試用例分為低級、中級、高級3個等級，參賽者對每一個測試用例都會得到1個百分制分數，使用加權平均分(低級權重為0.2，中級權重為0.3，高級權重為0.5)作為該參賽者的終究得分。
特別說明：在比賽早期，平臺只放出低級、中級的測試用例，故此時滿分為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

如果此時需要尋覓從0到1的路徑，且必須經過頂點2和3，我們會得到以下的路徑信息：

0,1,2|3

對該用例，可以找到以下兩條可行路徑:
1|5|4
2|6|3
由于第1條路徑的權重為4，第2條路徑的權重為5，所以此時最優解應當1|5|4。

運行環境

CPU：Intel Xeon CPU E5⑵690 V2 @ 3.00GHz
內存：2G
內核：單核
編譯器：gcc 4.8.4；java 1.7.0_95；
操作系統：linux Ubuntu 14.04.3 LTS 64位，內核版本 Linux version 3.13.0⑵4-gineric
SDK：為方便選手做題，分別提供c++(兼容c）和Java SDK包供參考（見賽題下載包），詳細描寫信息請見SDK目錄下的readme.txt。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 存儲空間管理

下一篇 打破摩爾定律：谷歌與騰訊的下一代計算平臺選擇是？

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

華為軟件精英挑戰賽2016題解