合肥生活安徽新聞合肥交通合肥房產(chǎn)生活服務(wù)合肥教育合肥招聘合肥旅游文化藝術(shù)合肥美食合肥地圖合肥社保合肥醫(yī)院企業(yè)服務(wù)合肥法律

        代寫Implementation of Graph Algorithms

        時(shí)間:2023-11-14  來源:合肥網(wǎng)hfw.cc  作者:hfw.cc 我要糾錯(cuò)


        C++ Implementation of Graph Algorithms

        1 Task Description

        You are asked to use C++ to solve the following puzzle.

        Hint: All it takes is an algorithm mentioned in this course (with a slight twist).

        The graph is undirected!

        2 Submission Guideline

        You must follow this guideline! Your submission will be marked automatically. Failure to

        follow this guideline will result in 0.

        Your submission should contain exactly one file: main.cpp.

        You do not need to submit a design.

        3 Puzzle

        You need to redesign the road system of an imaginary country.

        The country is composed of N cities (for simplicity numbered from 0 to N − 1). Some pairs of cities are

        connected by bidirectional roads. We say that there is a path between different cities A and B if there exists

        a sequence of unique cities C1, C2, . . . , CM, such that C1 = A and CM = B and for each index i < M, there

        is a road between cities Ci and Ci+1.

        The current state of the road network is miserable. Some pairs of cities are not connected by any path. On

        the other hand, other pairs of cities are connected by multiple different paths, and that leads to complicated

        traffic routing. You want to build some new roads and destroy some of the already existing roads in the

        country so that after the reconstruction there will exist exactly one path between every pair of distinct cities.

        As building new roads and destroying old ones costs a lot of money, you want to minimize the total cost

        spent on the reconstruction.

        You are given three two-dimensional arrays:

        • country[i][j]=1 or 0: there is an existing road between city i and j if and only if country[i][j]=1.

        • build[i][j]: the cost for building a road between i and j. The values of build[i][j] are represented

        using English letters. A, B, . . . , Z represent 0, 1, . . . , 25 and a, b, . . . , z represent 26, 27, . . . , 51. For

        example, if build[2][4]=b, then that means the cost for building a road between city 2 and city 4 is

        27.

        • destroy[i][j]: the cost for destroying a road between i and j. Again, the values are represented

        using English letters like the above.

        Your task is to find and print the minimal cost needed for the road network reconstruction.

        You don’t need to worry about invalid inputs.

        1

        • Sample input 1: 000,000,000 ABD,BAC,DCA ABD,BAC,DCA

        Note: 000,000,000 describes the two-dimensional array country. ABD,BAC,DCA describes the twodimensional array build. ABD,BAC,DCA describes the two-dimensional array destroy. The input

        format is: three strings separated by spaces; each string contains N parts separated by commas; each

        part contains N characters.

        Sample output 1: 3

        Comment: There are three cities, totally disconnected.

        • Sample input 2: 011,101,110 ABD,BAC,DCA ABD,BAC,DCA

        Sample output 2: 1

        Comment: Now the three cities form a connected triangle and we need to destroy one road. Optimal

        solution is to destroy the road between the cities 0-1 (cost 1).

        • Sample input 3: (note: all inputs are on the same line. I just couldn’t fit them in one line in this pdf.)

        011000,101000,110000,000011,000101,000110

        ABDFFF,BACFFF,DCAFFF,FFFABD,FFFBAC,FFFDCA

        ABDFFF,BACFFF,DCAFFF,FFFABD,FFFBAC,FFFDCA

        Sample output 3: 7

        Comment: We have six cities forming two separate triangles. Destroy one road in each triangle (costs

        1 for each road) and then join the triangles by a new road (costs 5).

        • Sample input 4: 0 A A

        Sample output 4: 0

        Comment: One city is okay just as it is.

        • Sample input 5: 0001,0001,0001,1110 AfOj,fAcC,OcAP,jCPA AWFH,WAxU,FxAV,HUVA

        Sample output 5: 0

        Comment: We have four cities, which are connected in such a way that there is exactly one path

        between each two cities.

        Thus there is nothing to reconstruct.

        4 Marking

        Marking will be done automatically. The total mark is 10 (1 for compiling and 9 for 9 test cases).

        5 Websubmission

        You are asked to submit via the web interface https://cs.adelaide.edu.au/services/websubmission/.

        The submission steps should be self-explanatory. Simply choose the correct semester, course, and assignment.

        The websubmission system will automatically fetch the latest version of your work from your SVN repository

        (you may also choose to submit older versions). Once your work is submitted, the system will launch a

        script checking the format of your submission. Click “View Feedback” to view the results. Your mark will

        be calculated offline after the deadline. You are welcome to resubmit for as many times as you wish (before

        the deadline).

        We will compile your code using g++ -o main.out -std=c++11 -O2 -Wall main.cpp. It is your responsibility to ensure that your code compiles on the university system.

        1

        1g++ has too many versions, so being able to compile on your laptop does not guarantee that it compiles on the university

        system. You are encouraged to debug your code on a lab computer (or use SSH).

        加QQ:99515681 或郵箱:99515681@qq.com   WX:codehelp

         

        掃一掃在手機(jī)打開當(dāng)前頁
      1. 上一篇:代寫CMPT 125、c++設(shè)計(jì)編程代做
      2. 下一篇:代寫CS170編程、代做Java程序設(shè)計(jì)
      3. 無相關(guān)信息
        合肥生活資訊

        合肥圖文信息
        急尋熱仿真分析?代做熱仿真服務(wù)+熱設(shè)計(jì)優(yōu)化
        急尋熱仿真分析?代做熱仿真服務(wù)+熱設(shè)計(jì)優(yōu)化
        出評(píng) 開團(tuán)工具
        出評(píng) 開團(tuán)工具
        挖掘機(jī)濾芯提升發(fā)動(dòng)機(jī)性能
        挖掘機(jī)濾芯提升發(fā)動(dòng)機(jī)性能
        海信羅馬假日洗衣機(jī)亮相AWE  復(fù)古美學(xué)與現(xiàn)代科技完美結(jié)合
        海信羅馬假日洗衣機(jī)亮相AWE 復(fù)古美學(xué)與現(xiàn)代
        合肥機(jī)場巴士4號(hào)線
        合肥機(jī)場巴士4號(hào)線
        合肥機(jī)場巴士3號(hào)線
        合肥機(jī)場巴士3號(hào)線
        合肥機(jī)場巴士2號(hào)線
        合肥機(jī)場巴士2號(hào)線
        合肥機(jī)場巴士1號(hào)線
        合肥機(jī)場巴士1號(hào)線
      4. 短信驗(yàn)證碼 酒店vi設(shè)計(jì) NBA直播 幣安下載

        關(guān)于我們 | 打賞支持 | 廣告服務(wù) | 聯(lián)系我們 | 網(wǎng)站地圖 | 免責(zé)聲明 | 幫助中心 | 友情鏈接 |

        Copyright © 2025 hfw.cc Inc. All Rights Reserved. 合肥網(wǎng) 版權(quán)所有
        ICP備06013414號(hào)-3 公安備 42010502001045

        主站蜘蛛池模板: 亚洲午夜精品一区二区麻豆| 一区二区3区免费视频| 亚洲一区二区影视| 无码精品不卡一区二区三区| 亚洲无线码一区二区三区| 大香伊蕉日本一区二区| 91视频一区二区| 无码精品人妻一区二区三区漫画| 鲁丝丝国产一区二区| 亚洲熟妇av一区| 中文字幕一区二区精品区| 国产一区二区中文字幕| 香蕉一区二区三区观| 亚洲国产精品成人一区| 老湿机一区午夜精品免费福利| 成人区人妻精品一区二区不卡| 大香伊人久久精品一区二区| 成人免费观看一区二区| 激情亚洲一区国产精品| 无码国产伦一区二区三区视频 | 日本精品高清一区二区2021| 国产香蕉一区二区精品视频| 亚洲国产老鸭窝一区二区三区| 免费日本一区二区| 91香蕉福利一区二区三区| 国产精品一级香蕉一区| 无码国产精品久久一区免费| 最新欧美精品一区二区三区| 国产av一区最新精品| 鲁大师成人一区二区三区| 日本一区二区三区免费高清在线| 高清一区高清二区视频| 精品人妻一区二区三区毛片| 精品人妻一区二区三区毛片 | 国产激情一区二区三区四区| 国产一区二区三区小向美奈子| 精品理论片一区二区三区| 国产伦精品一区二区三区免费下载| 免费无码一区二区| 国产精品无码一区二区三区电影| 精品一区二区三区在线成人|