數(shù)據(jù)結(jié)構(gòu)（Java語(yǔ)言版）-習(xí)題及答案 第8章圖習(xí)題答案

第8章圖習(xí)題參考答案 一、單選題ABCABCD./2124ABCABCDnn(n-1)C.nn/2.nABCABCDnn(n-1)C.nn/2.nABCABCDnn+ln-1n/2ABCABCDnn+ln-1n/2ABCABCD完全圖連通圖非連通圖以上都不對(duì)ABCABCD01n-1nABCABCD01n-1nABCABCD無(wú)向圖有向圖無(wú)向圖或有向圖以上都不對(duì)ABC一個(gè)圖的鄰接矩陣不是對(duì)稱矩陣，則該圖可能是ABC無(wú)向圖有向圖無(wú)向圖或有向圖D以上都不對(duì)DABCABCD有向圖無(wú)向圖無(wú)向圖或有向圖以上都不對(duì)ABCABCDn.n2C.n1.n2ABCABCDn2ne2eABCABCD與圖的頂點(diǎn)和邊數(shù)有關(guān)只與圖的邊數(shù)有關(guān)只與圖的頂點(diǎn)數(shù)有關(guān)與邊數(shù)的平方有關(guān)ABCABCD頂點(diǎn)v的度頂點(diǎn)v的出度頂點(diǎn)v的入度ABCABCD頂點(diǎn)v的度頂點(diǎn)v的出度頂點(diǎn)v的入度ABCABCD完全圖連通圖有回路一棵樹(shù)ABCABCD圖的遍歷是從給定的初始點(diǎn)出發(fā)訪問(wèn)每個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)僅訪問(wèn)一次圖的深度優(yōu)先遍歷適合無(wú)向圖圖的深度優(yōu)先遍歷不適合有向圖圖的深度優(yōu)先遍歷是一個(gè)遞歸過(guò)程無(wú)向圖=，E，其中=，b，c，d，e，，E=，b，，e，，c，b，e，c，，，d，e，d，下面對(duì)該圖進(jìn)行深度優(yōu)先遍歷得到的頂點(diǎn)序列正確的是 。Aa，b，e，c，d，fA

B.Ba，c，f，e，b，dCDC.，e，b，c，，CD.，e，d，，c，bABCABCDnn-1n+1不確定設(shè)有無(wú)向圖=，E和G=，;，如是的生成樹(shù)，則以下不正確的說(shuō)法是 。AABCD為的連通分量是的無(wú)環(huán)子圖為的子圖為的極小連通子圖且=VABCABCD由n-1條權(quán)值最小的邊構(gòu)成的子圖由n條權(quán)值之和最小的邊構(gòu)成的子圖由n個(gè)頂點(diǎn)構(gòu)成的極大連通子圖由n個(gè)頂點(diǎn)構(gòu)成的極小連通子圖，且邊的權(quán)值之和最小用r算法求一個(gè)連通的帶權(quán)圖的最小生成樹(shù)，在算法執(zhí)行的某時(shí)刻，已選取的頂點(diǎn)集合＝，，，已選取的邊的集合E＝，，(2，3)}，要選取下一條權(quán)值最小的邊，應(yīng)當(dāng)從 組邊中選取。ABCD.，，，，，，ABCD.，，，，，}C.，，，，，}.，，，，，，，}用r算法求一個(gè)連通的帶權(quán)圖的最小生成樹(shù)，在算法執(zhí)行的某時(shí)刻，已選取的頂點(diǎn)集合＝，，，邊的集合E＝，，(2，3)}，要選取下一條權(quán)值最小的邊，不可能從 組中選取。ABCD.，，，，，，ABCD.，，，，，}C.，，，，，}.，，，，，，，}

用ruk算法求一個(gè)連通的帶權(quán)圖的最小生成樹(shù)，在算法執(zhí)行的某時(shí)刻，已選取的邊集合E＝，，，，，，要選取下一條權(quán)值最小的邊，不可能選取的邊是 。AABCD.，).，)C.，).，)對(duì)某個(gè)帶權(quán)連通圖構(gòu)造最小生成樹(shù)，以下說(shuō)法中正確的是 。Ⅰ該圖的所有最小生成樹(shù)的總代價(jià)一定是唯一的Ⅱ其所有權(quán)值最小的邊一會(huì)出現(xiàn)在所有的最小生成樹(shù)中Ⅲ用普里姆（r）算法從不同頂點(diǎn)開(kāi)始構(gòu)造的所有最小生成樹(shù)一定相同Ⅳ使用普里姆算法和克魯斯卡爾（ruk）算法得到的最小生成樹(shù)總不相同AABCD僅Ⅰ僅Ⅱ僅Ⅰ、ⅢⅡ、ⅣABn個(gè)頂點(diǎn)e條邊的帶權(quán)有向圖采用鄰接矩陣存儲(chǔ)，求最短路徑的kr算法的時(shí)間復(fù)雜度為 。ABCDOn).On+eCDC.On).One)ABCDkrABCD按長(zhǎng)度遞減的順序按長(zhǎng)度遞增的順序通過(guò)深度優(yōu)先遍歷通過(guò)廣度優(yōu)先遍歷用kr算法求一個(gè)帶權(quán)有向圖中從頂點(diǎn)出發(fā)的最短路徑，在算法執(zhí)行的某時(shí)刻，S=，，，，下一步選取的目標(biāo)頂點(diǎn)可能是 。AABCD頂點(diǎn)2頂點(diǎn)3頂點(diǎn)4用kr算法求一個(gè)帶權(quán)有向圖中從頂點(diǎn)出發(fā)的最短路徑，在算法執(zhí)行的某時(shí)刻，S=，，，，則以后可能修改最短路徑是 。AABCD從頂點(diǎn)0到頂點(diǎn)2的最短路徑從頂點(diǎn)0到頂點(diǎn)3的最短路徑從頂點(diǎn)0到頂點(diǎn)4的最短路徑的最短路徑有一個(gè)頂點(diǎn)編號(hào)為～的帶權(quán)有向圖，現(xiàn)用Fyd算法求任意兩個(gè)頂點(diǎn)之間的最短路徑，在算法執(zhí)行的某時(shí)刻，已考慮了～的頂點(diǎn)，現(xiàn)慮頂點(diǎn)3，則以下敘述中正確的是 。AABCD只可能修改從頂點(diǎn)0～2到頂點(diǎn)3的最短路徑只可能修改從頂點(diǎn)3到頂點(diǎn)0～2的最短路徑只可能修改從頂點(diǎn)0～2到頂點(diǎn)4的最短路徑所有其他兩個(gè)頂點(diǎn)之間的路徑都可能被修改ABCD在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)i在頂點(diǎn)ABCD中有邊<，>G中有一條從頂點(diǎn)i到頂點(diǎn)j的路徑中沒(méi)有邊<，>G中有一條從頂點(diǎn)j到頂點(diǎn)i的路徑ABCABCD存在，且唯一存在、且不唯一存在，可能不唯一無(wú)法確定是否存在ABCABCD是個(gè)有根有向圖是個(gè)強(qiáng)連通圖含有多個(gè)入度為0的頂點(diǎn)含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量以下關(guān)于圖拓?fù)渑判虻臄⑹鲋姓_的是 。Ⅰ任何無(wú)環(huán)的有向圖，其頂點(diǎn)都可以排在一個(gè)拓?fù)湫蛄兄小＂蛉鬾個(gè)頂點(diǎn)的有向圖有唯一的撲序列，則其邊數(shù)必為n-1。Ⅲ.在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條邊<a，b>AABCD僅Ⅰ僅Ⅰ、Ⅲ僅Ⅱ、Ⅲ.Ⅰ、Ⅱ和ⅢABCABCD一個(gè)拓?fù)湫蛄袩o(wú)序的逆拓?fù)湫蛄邪错旤c(diǎn)編號(hào)次序ABCABCD從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑從源點(diǎn)到匯點(diǎn)的最短路徑最長(zhǎng)的回路最短的回路ABCD示工程的ABCD必須是唯一的可以有多條可以沒(méi)有以上都不對(duì)ABCD于ABCD在AOE網(wǎng)中可能存在多條關(guān)鍵路徑關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間任何一個(gè)關(guān)鍵活動(dòng)提前完成，整個(gè)工程也將提前完成所有關(guān)鍵活動(dòng)都提前完成，整個(gè)工程也將提前完成ABCABCD訪問(wèn)圖的所有頂點(diǎn)以某種次序訪問(wèn)圖的所有頂點(diǎn)從一個(gè)頂點(diǎn)出發(fā)訪問(wèn)圖中所有頂點(diǎn)且每個(gè)頂點(diǎn)只能訪問(wèn)一次從一個(gè)頂點(diǎn)出發(fā)訪問(wèn)圖中所有頂點(diǎn)但每個(gè)頂點(diǎn)可以訪問(wèn)多次ABCABCD圖的遍歷是從給定的初始點(diǎn)出發(fā)訪問(wèn)每個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)僅訪問(wèn)一次圖的深度優(yōu)先遍歷適合無(wú)向圖圖的深度優(yōu)先遍歷不適合有向圖圖的深度優(yōu)先遍歷是一個(gè)遞歸過(guò)程ABC以下（ABC遍歷拓?fù)渑判駾kr法DrABCABCD完全圖連通圖有回路一棵樹(shù)ABCD采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的ABCD先序遍歷中序遍歷后序遍歷層次遍歷ABCABCD1個(gè)2個(gè)任意多個(gè)0個(gè)ABCABCD./2124ABCABCDnn(n-1)C.nn/2.nABCABCDnn(n-1)C.nn/2.nABCABCDnn+ln-1n/2ABCABCD極小連通子圖極小子圖極大連通子圖極大子圖ABCABCDenn-e1ABCABCDn-1nn+12nABCABCDnn-1n+1不確定二、多選題ABCD在用r和ruk算法構(gòu)造最小生成樹(shù)時(shí)，前者更適合于①，后者更適合于ABCD有向圖無(wú)向圖稀疏圖稠密圖三、編程題OJ—求最長(zhǎng)路徑長(zhǎng)度問(wèn)題時(shí)間限制：，空間限制：。問(wèn)題描述：在聽(tīng)說(shuō)美國(guó)肥胖流行之后，農(nóng)夫約翰希望他的奶牛能夠做更多運(yùn)動(dòng)，因此他為他的奶牛提交了馬拉松申請(qǐng)，馬拉松路線包括一序列農(nóng)場(chǎng)對(duì)和它們之間的道路組成的路徑。由于約翰希望奶牛盡可能多地運(yùn)動(dòng)，他想在地圖上找到彼此距離最遠(yuǎn)的兩個(gè)農(nóng)場(chǎng)（距離是根據(jù)兩個(gè)農(nóng)場(chǎng)之間的道路上的道路總長(zhǎng)度來(lái)衡量的）。請(qǐng)你幫助他確定這對(duì)最遠(yuǎn)的農(nóng)場(chǎng)之間的距離。輸入格式：行1：兩個(gè)以空格分隔的整數(shù)：n和m。行+行：每行包含四個(gè)空格分隔的元素，x，y，和d描述一條道路，其中x和y是一條長(zhǎng)度為的道路相連的兩個(gè)農(nóng)場(chǎng)的編號(hào)，d是一個(gè)字符N、E、S或，表示從x到y(tǒng)的道路方向。輸出格式：給出最遠(yuǎn)的一對(duì)農(nóng)場(chǎng)之間距離的整數(shù)。答：prtvng*;prtvu*;prtvuScnner;csENde //邊數(shù)組元素類(lèi){ntv; //鄰接點(diǎn)nt; //邊權(quán)值ntnex; //下一條邊ENdentvnt) //構(gòu)造方{h=;}}pubccsn{cnt=;cnt;cn]ved=newn;cn]d=newn;//存放路徑長(zhǎng)度cntn; //存放結(jié)果cntn; //cnhed=newn;cENde]edge=newENde*;cvdddEdgentuntvnt)//無(wú)向圖添加<uv>和<vu>{edge=newENdev;//添加邊<uv>edgenex=hedu;hedu=++;edge=newENdeu;//添加邊<vu>edgenex=hedv;hedv=++;}cntFSntx) //從頂點(diǎn)x出發(fā)廣度優(yōu)先遍歷{rryved;rryd;Queue<neger>qu=newnked<neger>;vedx=;qu.offer(x);ntp=;hequEpy){ntu=qup;fdu>n) //求距離頂點(diǎn)x最大距離的頂點(diǎn)p{p=u;}rnte=hedu;e=;e=edgeenex){ntnt=edgee;fvedv==){vedv=;dv=du+;qu.offer(v);}}}p;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntxy;Srngd;rryhed;=;n=nnexIn;=nnexIn;rnt=;i<=;++){x=nnexIn;y=nnexIn;=nnexIn;d=nnex;ddEdgexy;}n=;ntn=;FSp; //從頂點(diǎn)pSyeuprnnn;}}.HDU4514—：6000ms，空間限制：65535K。問(wèn)題描述：隨著杭州西湖的知名度的進(jìn)一步提升，園林規(guī)劃專(zhuān)家湫湫希望設(shè)計(jì)出一條新的經(jīng)典觀光線路，根據(jù)老板馬小騰的指示，新的風(fēng)景線最好能建成環(huán)形，如果沒(méi)有條件建成環(huán)形，那就建的越長(zhǎng)越好?，F(xiàn)在已經(jīng)勘探確定了n個(gè)位置可以用來(lái)建設(shè)，在它們之間也勘探確定了m條可以設(shè)計(jì)的路線以及長(zhǎng)度。請(qǐng)問(wèn)是否能夠建成環(huán)形的風(fēng)景線？如果不能，風(fēng)景線最長(zhǎng)能夠達(dá)到多少？其中，可以興建的路線均是雙向的，它們之間的長(zhǎng)度均大于0n和m，其含義參見(jiàn)題目描述，接下去m行，每行3個(gè)數(shù)字u、v和，分別代表這條線路的起點(diǎn)、終點(diǎn)和長(zhǎng)度。有n≤，≤，≤u，v≤n，≤。輸出格式：對(duì)于每組測(cè)試數(shù)據(jù)，如果能夠建成環(huán)形（并不需要連接上去全部的風(fēng)景點(diǎn)），那么輸出YES，否則輸出最長(zhǎng)的長(zhǎng)度，每組數(shù)據(jù)輸出一行。答：prtvng*;prtvu*;prtvuScnner;csENde //邊數(shù)組元素類(lèi){ntv; //鄰接點(diǎn)nt; //邊權(quán)值ntnex; //下一條邊ENdentvnt) //構(gòu)造方{hv=hw=;}}pubccsn{cnt=;cntE=;cnt;cnher=newn;//并查集存儲(chǔ)結(jié)構(gòu)cnrnk=newn;//秩cntn;cnthed=newn;cENdeedge=newENdeE;cvdIn //初始化{rnt=;i<=n;++)her=;rryrnk;=;rryhed;}cntFndntx) //并查集查找{fherx==x)returnx;herx=Fndherx;returnfather[x];}cvdnnntrntrb)//并查集合并{frnkr>rnkrb)herrb=r;ee{frnkr==rnkrb)rnkrb++;herr=rb;}}cntved=newn;cntx=ver;cntrecrd=newn;cvdFSntu,ntd)//FS遍歷{vedu=;recrdu=;fx<d){ver=u;x=d;}rnte=hedu;e=;e=edgeenex){ntv=edgeev;fvedv==)FSvd+edgee;}}cvdddEdgentuntvnt)//無(wú)向圖添加<uv>和<vu>{edge=newENdev,;edgenex=hedu;hedu=++;edge=newENdeu,;edgenex=hedv;hedv=++;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;henhNex){n=nnexIn;=nnexIn;ntrrbuv;benrk=e;nt;In;r=;i<=;++){u=nnexIn;v=nnexIn;=nnexIn;r=Fndu;rb=Fndv;fr==rb) //存在回路{rk=rue;break;}nnrrb;//合并ddEdgeuv;//}r=+;i<=;++)//中途確定有回路后還需獲取其他邊{u=nnexIn;v=nnexIn;=nnexIn;}frk) //有回路的情況Syeuprnn"ES";ee //沒(méi)有回路的情況{rryrecrd;ntn=; //存放結(jié)果r=;i<=n;++)//從每個(gè)頂點(diǎn)出發(fā)搜索{frecrd==)//不搜索重復(fù)的頂點(diǎn)cnnue;rryved;x=;FS;//查找頂點(diǎn)的最遠(yuǎn)頂點(diǎn)vertrryved;x=;FSver;//查找頂點(diǎn)ver的最遠(yuǎn)頂點(diǎn)n=hxnx;}Syeuprnnn;}}}}OJ—高速公路問(wèn)題時(shí)間限制：，空間限制：。問(wèn)題描述：某島國(guó)完全平坦，不幸的是高速公路系統(tǒng)非常糟糕，當(dāng)?shù)卣庾R(shí)到了這個(gè)問(wèn)題，并且已經(jīng)建造了連接一些最重要城鎮(zhèn)的高速公路。但是，仍有一些城鎮(zhèn)無(wú)法通過(guò)高速公路抵達(dá)，所以有必要建造更多的高速公路讓任何兩個(gè)城鎮(zhèn)之間通過(guò)高速公路連接。所有城鎮(zhèn)的編號(hào)從到n，城鎮(zhèn)的位置由笛卡爾坐標(biāo)（x，y）給出。每條高速公路連接兩個(gè)城鎮(zhèn)。所有高速公路都直線相連，因此它們的長(zhǎng)度等于城鎮(zhèn)之間的笛卡爾距離。所有高速公路都是雙向的。高速公路可以自由地相互交叉，但司機(jī)只能在連接高速公路的兩個(gè)城鎮(zhèn)進(jìn)行切換。政府希望最大限度地降低建設(shè)新高速公路的成本。但希望保證每個(gè)城鎮(zhèn)都能夠到達(dá)。由于地勢(shì)平坦，高速公路的成本總是與其長(zhǎng)度成正比。因此，最便宜的高速公路系統(tǒng)將是最小化總公路長(zhǎng)度的系統(tǒng)。輸入格式：輸入包括兩部分。第一部分描述了該國(guó)的所有城鎮(zhèn)，第二部分描述了所有已建成的高速公路。輸入文件的第一行包含一個(gè)整數(shù)n（≤n≤）表示城鎮(zhèn)數(shù)量。接下來(lái)的n行每行包含兩個(gè)整數(shù)x和y，由空格分隔，給出了第個(gè)城鎮(zhèn)的坐標(biāo)（從到n）。坐標(biāo)的絕對(duì)值不超過(guò)，每個(gè)城鎮(zhèn)都有一個(gè)獨(dú)特的位置。下一行包含單個(gè)整數(shù)（≤≤），表示現(xiàn)有高速公路的數(shù)量。接下來(lái)的m行每行包含一對(duì)由空格分隔的整數(shù)，這兩個(gè)整數(shù)給出了一對(duì)已經(jīng)通有高速公路的城鎮(zhèn)編號(hào)，每對(duì)城鎮(zhèn)至多由一條高速公路連接。輸出格式：輸出所有要新建的高速公路，每條輸出一行，以便連接所有城鎮(zhèn)，盡可能減少新建高速公路的總長(zhǎng)度。如果不需要新建高速公路（所有城鎮(zhèn)都已連接），則輸出為空。答：prtvng*;prtvu*;prtvuScnner;pubccsn{cnlntINF=x;//表示∞cntn;cn]x; //城鎮(zhèn)的x坐標(biāo)cn]y; //城鎮(zhèn)的y坐標(biāo)cn]; //鄰接矩陣cvdrntv) //r算{n]c=newnn;n]ce=newnn;rnt=;i<n;++)c=v;cv=; //將頂點(diǎn)v添加到中rnt=;i<n;++) //取n個(gè)頂點(diǎn)到{ntn=INFk=;rnt=;j<n;++){c=&c]<n){n=c;k=;}}n=) //輸出一條邊Syeuprnncek++""+k+;ck=; //將頂點(diǎn)k添加到中rnt=;j<n;++){c=1&k]<c){c=k;ce=k;}}}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;n=nnexIn;x=newnn;y=newnn;=newnnn;rnt=;i<n;++) //輸入n個(gè)城鎮(zhèn){x=nnexIn;y=nnexIn;}rnt=;i<n;++) //rnt=;j<n;++){ntd=xx*xx+yy*yy;==d;}=nnexIn; //輸入rnt=;i<;++){ntx=nnexIn;nty=nnexIn;xy=yx=;//將路徑長(zhǎng)度置為0}r; //從頂點(diǎn)出發(fā)構(gòu)造最小生成樹(shù)}}.OJ—重型運(yùn)輸問(wèn)題時(shí)間限制：，空間限制：。問(wèn)題描述：Hug很高興，在Crger項(xiàng)目失敗后他現(xiàn)在可以擴(kuò)展業(yè)務(wù)了。但他需要一個(gè)聰明的人告訴他，能不能將貨物運(yùn)輸?shù)街付ǖ目蛻舨⑶覞M足經(jīng)過(guò)的道路的最大承載量。幸運(yùn)的是，他已經(jīng)有了城市中所有街道和橋梁的最大承載量，不幸的是，他不知道如何找到最大運(yùn)輸重量。請(qǐng)你幫助Hugo，給你城市的規(guī)劃圖，描述了各交叉點(diǎn)之間的街道（具有最大承載量），交叉點(diǎn)的編號(hào)從1到n。你的任務(wù)是找到從1（Hugo的位置）到n號(hào)（客戶的位置）交叉點(diǎn)可以運(yùn)輸?shù)淖畲笾亓?，你可以假設(shè)至少有一條路徑。所有街道都是雙向通行。輸入格式：第一（城市圖）。對(duì)于每個(gè)城市，第一行給出街道交叉點(diǎn)的數(shù)量n（1≤n≤1000）和街道的數(shù)量m，以下m行每行是一個(gè)整數(shù)三元組，指定街道開(kāi)始和結(jié)束交叉點(diǎn)編號(hào)和允許的最大重量，它是正數(shù)且不大于1000000，每對(duì)交叉點(diǎn)之間最多只有一條街道。輸出格式：每個(gè)場(chǎng)景的輸出以"Scenro#："開(kāi)頭，其中是從開(kāi)始的場(chǎng)景編號(hào)，然后輸出一行，其中包含Hug個(gè)空行表示輸出結(jié)束。答：prtvng*;prtvu*;csNde //優(yōu)先隊(duì)列（按d大根堆）中結(jié)點(diǎn)類(lèi)型{ntv; //頂點(diǎn)編號(hào)ntd; //dv值pubcNdentvntd) //構(gòu)造方法{hv=v;hd=d;}}csENde //邊類(lèi){ntv; //鄰接點(diǎn)nt; //邊權(quán)值ntnex; //下一條邊ENdentvnt) //構(gòu)造方{h=;}}pubccsn{cnlntINF=x;//表示∞cnlnt=; //表示最多頂點(diǎn)個(gè)數(shù)cnlntE=*;//表示最多頂點(diǎn)個(gè)數(shù)cnt;cn]hed=newn;cENde]edge=newENdeE;cntn;cvdddEdgentuntvnt)//無(wú)向圖添加<uv和<vu>{edge=newENdev;//添加邊<uv>edgenex=hedu;hedu=++;edge=newENdeu;//添加邊<vu>edgenex=hedv;hedv=++;}pubccntkrntv)//求從v到其他頂點(diǎn)的最短路徑{Cprr<Nde>dCprr//定義dCprr=newCprr<Nde>){pubcntcpreNdeNde)//用于創(chuàng)建d大根堆{reurndd;}};rryQueue<Nde>pq=newrryQueue<Nde>dCprr;nd=newn;//建立d數(shù)組n]S=newn; //建立S數(shù)rryd; //初始化d]rryS;dv=INF; //源點(diǎn)到自己的最大承載量看成∞pqernewNdevdv;//將頂點(diǎn)v進(jìn)隊(duì)pqhepqEpy) //隊(duì)不空循環(huán){Ndep=pqp; //出隊(duì)結(jié)點(diǎn)pntu=pv; //選取具有最大d的頂點(diǎn)ufSu==)cnnue;//跳過(guò)S中的頂點(diǎn)uSu=; //頂點(diǎn)u加入S中fu==n)brek; //找到頂點(diǎn)n，結(jié)束rnte=hedu;e=;e=edgeenex){ntv=edgeev; //找到邊nt=edgee;fSv==) //修改不在S中的頂點(diǎn)v的dfdv]<hndu{dv=hndu;pqernewNdevdv;}}}reurndn;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntb;=nnexIn;rntk=;k<=;k++){rryhed;=;n=nnexIn;=nnexIn;rnt=;i<=;++) //輸入條邊的信息{=nnexIn;b=nnexIn;=nnexIn;ddEdgeb;}Syeuprn"Scenro#%d:\n"k;//輸出結(jié)果Syeuprn"%d\n\n"kr;}}}.OJ—股票經(jīng)紀(jì)人的小道消息問(wèn)題時(shí)間限制：，空間限制：。問(wèn)題描述：眾所周知，股票經(jīng)紀(jì)人對(duì)謠言會(huì)反應(yīng)過(guò)度。你已經(jīng)簽約開(kāi)發(fā)一種在股票經(jīng)紀(jì)人中傳播虛假信息的方法，以便為你的雇主提供股票市場(chǎng)的戰(zhàn)術(shù)優(yōu)勢(shì)。為了達(dá)到最大效果，你必須以最快的方式傳播謠言。不幸的是，股票經(jīng)紀(jì)人只信任來(lái)自他們“可信來(lái)源”的信息，這意味著你必須在傳播謠言時(shí)考慮他們的聯(lián)系人的結(jié)構(gòu)。特定的股票經(jīng)紀(jì)人需要一定的時(shí)間才能將謠言傳遞給他的每個(gè)同事。你的任務(wù)是編寫(xiě)一個(gè)程序，告訴你選擇哪個(gè)股票經(jīng)紀(jì)人作為謠言的起點(diǎn)，以及謠言傳播到股票經(jīng)紀(jì)人社區(qū)所需的時(shí)間。該持續(xù)時(shí)間是指最后一個(gè)人接收信息所需的時(shí)間。輸入格式：你的程序?qū)椴煌墓善苯?jīng)紀(jì)人輸入數(shù)據(jù)。每組都以一條包含股票經(jīng)紀(jì)人數(shù)量n的行開(kāi)頭，接下來(lái)每行一個(gè)股票經(jīng)紀(jì)人，其中包含與之聯(lián)系的人數(shù)，這些人是誰(shuí)，以及他們將消息傳遞給每個(gè)人所花費(fèi)的時(shí)間。每個(gè)股票經(jīng)紀(jì)人行的格式如下：該行以聯(lián)系人數(shù)量（m）開(kāi)頭，后跟n對(duì)整數(shù)，每個(gè)聯(lián)系人一對(duì)。每一對(duì)首先列出一個(gè)指代聯(lián)系人的號(hào)碼（例如1表示該組中的第一個(gè)號(hào)碼），然后是用于將消息傳遞給該人的時(shí)間（以分鐘為單位）。沒(méi)有特殊的標(biāo)點(diǎn)符號(hào)或間距規(guī)則。每個(gè)人的編號(hào)為1到股票經(jīng)紀(jì)人的數(shù)量。傳遞消息所需的時(shí)間將介于1到10分鐘（包括1和10分鐘）之間，聯(lián)系人數(shù)量將介于0到股票經(jīng)紀(jì)人的數(shù)量減1之間。股票經(jīng)紀(jì)人的數(shù)量范圍從1到100，輸入由一組包含0個(gè)股票經(jīng)紀(jì)人終止。輸出格式：對(duì)于每組數(shù)據(jù)，你的程序必須輸出一行，其中包含導(dǎo)致最快消息傳輸?shù)娜?，以及在你將該消息傳遞給此人之后最后一個(gè)人收到任何給定消息的時(shí)間，以整數(shù)分鐘為單位。你的程序可能會(huì)收到一個(gè)排除某些人的連接網(wǎng)絡(luò)，即某些人可能無(wú)法訪問(wèn)。如果你的程序檢測(cè)到這樣一個(gè)破碎的網(wǎng)絡(luò)，只需輸出消息dn。注意，將消息從傳遞給所花費(fèi)的時(shí)間不一定與將其從傳遞給所花費(fèi)的時(shí)間相同。答：prtvng*;prtvu*;prtvuScnner;pubccsn{cnlnt=; //表示最多經(jīng)紀(jì)人個(gè)cnlntINF=x; //表示∞cn]=newn;//數(shù)組，初始為鄰接矩陣cntn; //經(jīng)紀(jì)人個(gè)數(shù)pubccvdFyd //Fyd算法{rntk=;k<=n;k++) //求k]{rnt=;i<=n;++)rnt=;j<=n;++)f=j&>k+k)=k+k;}}pubccvddpn //求結(jié)果并且輸出{ntx;ntntnv=;rnt=;i<=n;++) //以點(diǎn)作為各通路源點(diǎn){x=;rnt=;j<=n;++)=j&x< //找到x=;n>x){n=x; //找最長(zhǎng)路徑中的最短路徑長(zhǎng)nv=; //該最短長(zhǎng)度路徑的源點(diǎn)}}n<NF) //源點(diǎn)nvSyeuprnnnv+""+n;ee //源點(diǎn)nvSyeuprnn"dn";}pubccvdnSrng]rg){Scnnern=newScnnerSyen;henhNex){n=nnexIn;fn==)brek;rnt=;i<=n;++) //rnt=;j<=n;++)f==)=;ee=INF;rnt=;i<=n;++) //輸入鄰接矩陣A{nt=nnexIn;rnt=;j<=;++){ntp=nnexIn;nt=nnexIn;p=;}}Fyd; //調(diào)用Fyd算法求Adpn; //求nv和n并且輸}}}H—重新排列指令問(wèn)題時(shí)間限制：，空間限制：。問(wèn)題描述：阿里本學(xué)期開(kāi)設(shè)了計(jì)算機(jī)組織與架構(gòu)課程，他了解到指令之間可能存在依賴關(guān)系，如WAR（寫(xiě)入后讀?。?，WAW，RAW。如果兩個(gè)指令之間的距離小于安全距離（Sence），則會(huì)導(dǎo)致危險(xiǎn)，這可能導(dǎo)致錯(cuò)誤的結(jié)果，所以需要設(shè)計(jì)特殊的電路以消除危險(xiǎn)。然而，解決此問(wèn)題的最簡(jiǎn)單方法是添加氣泡（無(wú)用操作），這意味著浪費(fèi)時(shí)間以確保兩條指令之間的距離不小于安全距離。兩條指令之間距離的定義是它們的開(kāi)始時(shí)間之間的差異?，F(xiàn)在有很多指令，已知指令之間的依賴關(guān)系和安全距離。我們有一個(gè)非常強(qiáng)大的CPU，具有無(wú)限數(shù)量的內(nèi)核，因此你可以根據(jù)需要同時(shí)運(yùn)行多個(gè)指令，并且CPU速度非?？欤恍杌ㄙM(fèi)1ns即可完成任何指令。你的工作是重新排列指令，以便CPU可以使用最短的時(shí)間完成所有指令。輸入格式：輸入包含幾個(gè)測(cè)試用例。每個(gè)測(cè)試用例的第一行是兩個(gè)整數(shù)n，（n≤，≤），表示有n個(gè)指令和m個(gè)依賴關(guān)系，以下m行，每行包含三個(gè)整數(shù)x，y，z，表示x和y之間的安全距離為z，y應(yīng)在x之后運(yùn)行。指令編號(hào)從0到n-1。輸出格式：每個(gè)測(cè)試用例打印一個(gè)整數(shù)，即CPU運(yùn)行所需的最短時(shí)間。答：prtvng*;prtvu*;prtvuScnner;csENde //邊類(lèi)型{ntv; //鄰接點(diǎn)nt; //邊權(quán)值ntnex; //下一條邊ENdentvnt) //構(gòu)造方{h=;}}pubccsn{cnlntINF=x; //表示∞cnlnt=; //表示最多頂點(diǎn)個(gè)數(shù)cnlntE=*;//表示最多頂點(diǎn)個(gè)數(shù)cnt;cn]hed=newn;cENde]edge=newENdeE;cnnd=newn; //記錄每個(gè)頂點(diǎn)的入度cnc=newn; //記錄到頂點(diǎn)cntn;cvdddEdgentuntvnt)//有向圖添加邊<uv>{edge=newENdev;edgenex=hedu;hedu=++;ndv++; //頂點(diǎn)v的入度增1}pubccvdpSr //拓?fù)渑判騵Sck<neger>=newSck<neger>;//定義一個(gè)棧rnt=;i<n;++) //所有入度為的頂點(diǎn)進(jìn)棧fnd==){puh;c=; //路徑經(jīng)過(guò)頂點(diǎn)，長(zhǎng)度計(jì)為1}heepy //棧不為空時(shí)循環(huán){ntu=pp; //出棧一個(gè)頂點(diǎn)urnte=hedu;e=;e=edgeenex){ntnt=edgee;ndv;cv=hxcvcu+;fndv==) //入度為的頂點(diǎn)進(jìn)棧st.push(v);}}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;henhNex){rryhed; //=;rrynd; //頂點(diǎn)入度初始化rryc; //頂點(diǎn)的最長(zhǎng)路徑長(zhǎng)度初始n=nnexIn;=nnexIn;rnt=;i<=;++) //輸入邊的信息{ntu=nnexIn;ntv=nnexIn;nt=nnexIn;ddEdgeuv;}TopSort();ntrnt=;i<n;++) //cn=hxnc;Syeuprnnn;}}}OJ—城堡問(wèn)題時(shí)間限制：，空間限制：。問(wèn)題描述：如圖所示的城堡中#表示墻，請(qǐng)你編寫(xiě)一個(gè)程序，計(jì)算城堡一共有多少房間，最大的房間有多大？城堡被分割成n（≤，n≤）個(gè)方塊，每個(gè)方塊可以有~面墻。輸入格式：程序從標(biāo)準(zhǔn)輸入設(shè)備讀入數(shù)據(jù)。第一行是兩個(gè)整數(shù)，分別是南北向、東西向的方塊數(shù)。在接下來(lái)的輸入行里，每個(gè)方塊用一個(gè)數(shù)字（0≤p≤50）描述，1表示西墻，2表示北墻，4表示東墻，8表示南墻。每個(gè)方塊的數(shù)字是其周?chē)鷫Φ臄?shù)字之和表示。城堡的內(nèi)墻被計(jì)算兩次，方塊（1，1）的南墻同時(shí)也是方塊（2，1）的北墻。輸入的數(shù)據(jù)保證城堡至少有兩個(gè)房間。輸出格式：輸出兩個(gè)整數(shù)，前者表示城堡的房間數(shù)，后者表示城堡中最大房間包括的方塊數(shù)。答：prtvng*;prtvu*;prtvuScnner;pubccsn{cnt=; //最大行列數(shù)cnp=newn;//存放方塊cncr=newn;//方塊是否染過(guò)色cntNu=xre=;//房間數(shù)和最大方塊數(shù)cntre; //當(dāng)前房間的方塊數(shù)cvdFSntnt) //從查找包含它的房間{cr=) //已經(jīng)染過(guò)色，返回return;re++; //顏色數(shù)增加1cr=Nu;p]&==) //沒(méi)有西墻FS;p]&==) //沒(méi)有北墻FS;p]&==) //沒(méi)有東墻FS+;p]&==) //沒(méi)有南墻FS+;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;=nnexIn;n=nnexIn;rnt=;i<=;++)rnt=;j<=n;++)p=nnexIn;rnt=;i<=;++)rnt=;j<=n;++)fcr==){Nu++;re=;//房間的方塊數(shù)初始化為0FS;xre=hxxrere;}SyeuprnnNu;Syeuprnnxre;}}四、簡(jiǎn)答題.某城市道路中大部分是雙向馬路，有少部分是單向馬路?，F(xiàn)構(gòu)建該城市道路交通網(wǎng)用于道路規(guī)劃，包括道路查找等。問(wèn)是設(shè)計(jì)成有向圖還是無(wú)向圖？是帶權(quán)圖還是不帶權(quán)圖？答：因?yàn)槌鞘械缆分杏袉蜗蝰R路，只能用有向邊來(lái)表示，雙向馬路可以轉(zhuǎn)換成兩條有向邊。另外，在道路規(guī)劃中涉及馬路的長(zhǎng)度，所以該城市道路交通網(wǎng)應(yīng)設(shè)計(jì)成帶權(quán)有向圖。有一個(gè)無(wú)向連通圖，對(duì)于給定的某種鄰接表表示，能否通過(guò)修改深度優(yōu)先遍歷算法求出所有的深度優(yōu)先遍歷序列？ 答：不能。對(duì)于給定的無(wú)向連通圖鄰接表，其表示是不唯一的，不同的鄰接表，通過(guò)修改深度優(yōu)先遍歷算法只能求出該鄰接表下所有的深度優(yōu)先遍歷序列，除非構(gòu)建所有可能的鄰接表，才可能求出所有的深度優(yōu)先遍歷序列。圖的遍歷針對(duì)頂點(diǎn)，要求按一定順序訪問(wèn)圖中所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅訪問(wèn)一次。可否針對(duì)邊也使用遍歷算法？ 答：可以。用二維輔助數(shù)組ved來(lái)記錄一條邊是否訪問(wèn)過(guò)，初始時(shí)所有元素為。可以從任一頂點(diǎn)出發(fā)，對(duì)于訪問(wèn)的一條邊<>，置ved]=表示該邊已訪問(wèn)過(guò)，下次再找相鄰邊<k>時(shí)只有在vedk為時(shí)才從頂點(diǎn)k出發(fā)進(jìn)行遞歸調(diào)用。整個(gè)過(guò)程與頂點(diǎn)遍歷的深度優(yōu)先過(guò)程相同。圖的遍歷對(duì)無(wú)向圖和有向圖都適用嗎？ 答：圖的遍歷對(duì)無(wú)向圖和有向圖都適用。但如果無(wú)向圖不是連通的，或有向圖不是強(qiáng)連通的，調(diào)用一次遍歷算法只能訪問(wèn)一個(gè)連通分量或強(qiáng)連通分量中的頂點(diǎn)，這種情況下需要多次調(diào)用遍歷算法。圖的深度優(yōu)先遍歷類(lèi)似于樹(shù)的先根遍歷，可歸屬哪一類(lèi)算法？ 答：圖的深度優(yōu)先遍歷類(lèi)似于樹(shù)的先根遍歷，都屬于回溯算法。由于圖的深度優(yōu)先遍歷有可能在訪問(wèn)某個(gè)頂點(diǎn)后，沿著某條路徑向前搜索又回到這個(gè)頂點(diǎn)，所以要設(shè)置一個(gè)訪問(wèn)標(biāo)記數(shù)組ved記錄已訪問(wèn)過(guò)的頂點(diǎn)，以避免重復(fù)訪問(wèn)，而樹(shù)的先根遍歷沒(méi)有這種情形出現(xiàn)。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的連通無(wú)向圖，如果它有且只有一個(gè)簡(jiǎn)單回路，那么該圖有幾條邊？為什么？ 答：該圖有n條邊。因?yàn)榫哂衝個(gè)頂點(diǎn)n-1條邊的連通無(wú)向圖是樹(shù)圖，它沒(méi)有任何回路，但兩個(gè)頂點(diǎn)i和j之間有路徑，如果加上一條邊(i,j)，則形成一個(gè)簡(jiǎn)單回路，如果再加上一條邊，則會(huì)形成兩個(gè)簡(jiǎn)單回路。所以這樣的圖恰好有n條邊。7.有一個(gè)如圖8.1（a）所示的有向圖，回答以下問(wèn)題：（1）給出該圖的所有強(qiáng)連通分量。（2）給出從頂點(diǎn)0到頂點(diǎn)的所有簡(jiǎn)單路徑。答：（）該有向圖的強(qiáng)連通分量如圖（b）所示，共有個(gè)強(qiáng)連通分量。（2）頂點(diǎn)0到頂點(diǎn)的所有簡(jiǎn)單路徑如下：0→1→4→80→3→7→80→3→1→4→88.有一個(gè)如圖8.2（a）所示的有向圖，給出其所有的強(qiáng)連通分量。答：圖中頂點(diǎn)0、1、2構(gòu)成一個(gè)環(huán)，這個(gè)環(huán)一定是某個(gè)強(qiáng)連通分量的一部分，圖中頂點(diǎn)3、4構(gòu)成一個(gè)環(huán)，這個(gè)環(huán)也一定是某個(gè)強(qiáng)連通分量的一部分，這兩個(gè)環(huán)合在一起后能不能構(gòu)成一個(gè)強(qiáng)連通分量呢？通過(guò)判斷它們能夠構(gòu)成一個(gè)強(qiáng)連通分量。另外，頂點(diǎn)5、6各自構(gòu)成一個(gè)強(qiáng)連通分量。該有向圖的強(qiáng)連通分量有個(gè)，如圖（b）所示。9.一個(gè)圖有7個(gè)頂點(diǎn)，編號(hào)為0～6，其鄰接矩陣如下： 回答以下問(wèn)題：（1）畫(huà)出該有向圖。（2）求頂點(diǎn)0的入度和出度。求頂點(diǎn)2的度。答：（）該有向圖如圖所示。頂點(diǎn)0的入度為0，出度為3。頂點(diǎn)2的度為5。圖是一個(gè)非連通無(wú)向圖，共有條邊，則該圖至少有多少個(gè)頂點(diǎn)？ 答：由于G是一個(gè)非連通無(wú)向圖，在邊數(shù)固定時(shí)，頂點(diǎn)數(shù)最少的情況是該圖由兩個(gè)連通子圖構(gòu)成，且其中之一只含一個(gè)頂點(diǎn)，另一個(gè)為完全圖。其中只含一個(gè)頂點(diǎn)的子圖沒(méi)有邊，另一個(gè)完全圖的邊數(shù)為nn/，即：nn/=，得：n=。所以，該圖至少有+=個(gè)頂點(diǎn)。使用普里姆算法構(gòu)造出如圖所示的圖的一棵最小生成樹(shù)。答：11.已知帶權(quán)連通圖=（E）的鄰接表如圖所示，請(qǐng)畫(huà)出該圖的邏輯結(jié)構(gòu)，并分別以深度優(yōu)先和廣度優(yōu)先遍歷該圖，寫(xiě)出遍歷中頂點(diǎn)的序列，并畫(huà)出該圖的一棵最小生成樹(shù)，其中表結(jié)點(diǎn)的個(gè)域各為：答：該圖的邏輯結(jié)構(gòu)如圖所示。從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷序列為：0、1、2、3、4。從頂點(diǎn)1出發(fā)的廣度優(yōu)先遍歷序列為：0、1、2、3、4。采用普里姆算法（從頂點(diǎn)出發(fā)）或克魯斯卡爾算法求得的最小生成樹(shù)如圖所示。給出如圖所示的圖中從頂點(diǎn)開(kāi)始的深度優(yōu)先生成樹(shù)，并求出最小生成樹(shù)。答：從頂點(diǎn)0開(kāi)始的深度優(yōu)先遍歷序列很多，每一序列都生成一棵DFS樹(shù)，除去重復(fù)的，其深度優(yōu)先生成樹(shù)及權(quán)值之和如下：，，，，，權(quán)值和為++++=1，，，，，權(quán)值和為++++=2，，，，，權(quán)值和為++++=3，，，，，權(quán)值和為++++=4，，，，，權(quán)值和為++++=5，，，，，權(quán)值和為++++=1，，，，，權(quán)值和為++++=2，，，，，權(quán)值和為++++=5，，，，，權(quán)值和為++++=1，，，，，權(quán)值和為++++=8，，，，，權(quán)值和為++++=4其最小生成樹(shù)為，，，，。13.對(duì)于如圖所示的帶權(quán)無(wú)向圖，給出利用普里姆算法（從頂點(diǎn)開(kāi)始構(gòu)造）和克魯斯卡爾算法構(gòu)造出的最小生成樹(shù)的結(jié)果。答：利用普里姆算法從頂點(diǎn)出發(fā)構(gòu)造的最小生成樹(shù)為：。利用克魯斯卡爾算法構(gòu)造出的最小生成樹(shù)為：。

14.對(duì)于如下圖所示的帶權(quán)有向圖，采用Dijkstra算法求出從頂點(diǎn)0到其他各頂點(diǎn)的最短路徑及其長(zhǎng)度。答：采用Dijkstra算法求從頂點(diǎn)0到其他各頂點(diǎn)的最短路徑及其長(zhǎng)度如下：從0到1的最短路徑長(zhǎng)度為1，最短路徑為0->1。從0到2的最短路徑長(zhǎng)度為4，最短路徑為0->1->2。從0到3的最短路徑長(zhǎng)度為2，最短路徑為0->3。從0到4的最短路徑長(zhǎng)度為8，最短路徑為0->1->4。從0到5的最短路徑長(zhǎng)度為10，最短路徑為0->3->5。15.對(duì)于如下圖所示的頂點(diǎn)表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試問(wèn)建在哪個(gè)村莊能使各村莊總體的交通代價(jià)最??？答：采用Floyd算法求出兩頂點(diǎn)之間的最短路徑長(zhǎng)度，其鄰接矩陣如下：A=最后求得：

A從A4中求得每對(duì)村莊之間的最少交通代價(jià)。假設(shè)醫(yī)院建在村莊i，其他各村莊往返總的交通代價(jià)如下表所示。顯然把醫(yī)院建在村莊3總的交通代價(jià)最少。醫(yī)院建在的村莊各村莊往返總的交通代價(jià)012+16+4+7+13+16+4+18=90113+29+17+20+12+11+8+5=115216+11+12+6+16+29+12+34=13634+8+12+3+4+17+12+22=82418+5+34+22+7+20+6+3+0=11516.已知世界大城市為：北京（）、紐約（N）、巴黎（）、倫敦（）、東京（）、墨西哥城（）。試在由表給出的交通網(wǎng)中確定最小生成樹(shù)，并說(shuō)明所使用的方法及其時(shí)間復(fù)雜度。表1世界大城市交通里程網(wǎng)絡(luò)表單位:k)答：構(gòu)成的無(wú)向圖如圖所示。產(chǎn)生的最小生成樹(shù)如圖所示。使用普里姆算法的時(shí)間復(fù)雜度為On，其中n為圖中頂點(diǎn)個(gè)數(shù)。使用克魯斯卡爾算法的時(shí)間復(fù)雜度為Oege，其中e為圖的邊數(shù)。17.給出如下圖所示有向圖的所有拓?fù)湫蛄?。答：拓?fù)湫蛄杏衋ebcd、abced、abecd。18.如下圖所示的AOE網(wǎng)，求：（1）每項(xiàng)活動(dòng)ai的最早開(kāi)始時(shí)間e（ai）和最遲開(kāi)始時(shí)間l（ai）。（2）完成此工程最少需要多少天（設(shè)邊上的權(quán)值為天數(shù)）。（3）哪些是關(guān)鍵活動(dòng)。（4）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期。答：（1）該圖的一個(gè)拓?fù)湫蛄袨?，2，3，4，5，6，7，8，9，10。按此次序求所有事件的最早發(fā)生時(shí)間如下： ve(1)=0 ve(2)=5 ve(3)=6 ve(4)=MAX{ve(2)+3,ve(3)+6}=12 ve(5)=MAX{ve(3)+3,ve(4)+6}=15 ve(6)=ve(4)+4=16 ve(7)=ve(5)+1=16 ve(8)=ve(5)+4=19 ve(9)=MAX{ve(7)+5,ve(8)+2}=21 ve(10)=MAX{ve(6)+4,ve(9)+2}=23按拓?fù)渑判虻哪嫘蚯笏袝r(shí)間的最遲發(fā)生時(shí)間如下：vl(10)=23 vl(9)=vl(10)-2=21 vl(8)=vl(9)-2=19vl(7)=vl(9)-5=16 vl(6)=vl(10)-4=19 vl(5)=MIN{vl(7)-1,vl(8)-4}=15 vl(4)=MIN{vl(6)-4,vl(5)-3}=12vl(3)=MIN{vl(4)-6,vl(5)-3}=6 vl(2)=vl(4)-3=9 vl(1)=MIN{vl(2)-5,vl(3)-6}=0求所有活動(dòng)的e()、l()和d()如下：活動(dòng)a1：e(a1)=ve(1)=0 l(a1)=vl(2)-5=4 d(a1)=4活動(dòng)a2：e(a2)=ve(1)=0 l(a2)=vl(3)-6=0 d(a2)=0活動(dòng)a3：e(a3)=ve(2)=5 l(a3)=vl(4)-3=8 d(a3)=3活動(dòng)a4：e(a4)=ve(3)=6 l(a4)=vl(4)-6=6 d(a4)=0活動(dòng)a5：e(a5)=ve(3)=6 l(a5)=vl(5)-3=12 d(a5)=6活動(dòng)a6：e(a6)=ve(4)=12 l(a6)=vl(5)-3=12 d(a6)=0活動(dòng)a7：e(a7)=ve(4)=12 l(a7)=vl(6)-4=15 d(a7)=3活動(dòng)a8：e(a8)=ve(5