最小生成樹和拓?fù)渑判蛘n件

最小生成樹和7月18日最小生成樹和7月18日1最小生成樹最小生成樹2一、什么是圖的最小生成樹（MST）？

不知道大家還記不記得樹的一個(gè)定理：N個(gè)點(diǎn)用N-1條邊連接成一個(gè)連通塊，形成的圖形只可能是樹，沒有別的可能。

一個(gè)有N個(gè)點(diǎn)的圖，邊一定是大于等于N-1條的。圖的最小生成樹，就是在這些邊中選擇N-1條出來，連接所有的N個(gè)點(diǎn)。這N-1條邊的邊權(quán)之和是所有方案中最小的。一、什么是圖的最小生成樹（MST）？一個(gè)有N個(gè)點(diǎn)的圖，3二、最小生成樹用來解決什么問題？

就是用來解決如何用最小的“代價(jià)”用N-1條邊連接N個(gè)點(diǎn)的問題?！疽坑幸粡埑鞘械貓D，圖中的頂點(diǎn)為城市，無向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)特點(diǎn)，即任一對(duì)城市都是連通的。現(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計(jì)可使得工程的總造價(jià)最少？123452471162二、最小生成樹用來解決什么問題？就是用來解決如何用最4Prim算法算法分析&思想講解：Prim算法采用“藍(lán)白點(diǎn)”思想：白點(diǎn)代表已經(jīng)進(jìn)入最小生成樹的點(diǎn)，藍(lán)點(diǎn)代表未進(jìn)入最小生成樹的點(diǎn)。Prim算法每次循環(huán)都將一個(gè)藍(lán)點(diǎn)u變?yōu)榘c(diǎn)，并且此藍(lán)點(diǎn)u與白點(diǎn)相連的最小邊權(quán)min[u]還是當(dāng)前所有藍(lán)點(diǎn)中最小的。這樣相當(dāng)于向生成樹中添加了n-1次最小的邊，最后得到的一定是最小生成樹。我們通過對(duì)右圖最小生成樹的求解模擬來理解上面的思想。藍(lán)點(diǎn)和虛線代表未進(jìn)入最小生成樹的點(diǎn)、邊；白點(diǎn)和實(shí)線代表已進(jìn)入最小生成樹的點(diǎn)、邊。123452471162Prim算法算法分析&思想講解：1234524711625初始時(shí)所有點(diǎn)都是藍(lán)點(diǎn)，min[1]=0,min[2、3、4、5]=∞。權(quán)值之和MST=0。123452471162第一次循環(huán)自然是找到min[1]=0最小的藍(lán)點(diǎn)1。將1變?yōu)榘c(diǎn)，接著枚舉與1相連的所有藍(lán)點(diǎn)2、3、4，修改它們與白點(diǎn)相連的最小邊權(quán)。123452471162min[2]=w[1][2]=2;min[3]=w[1][3]=4;min[4]=w[1][4]=7;123452471162第一次循環(huán)自然是找到min[1]=06第二次循環(huán)是找到min[2]最小的藍(lán)點(diǎn)2。將2變?yōu)榘c(diǎn)，接著枚舉與2相連的所有藍(lán)點(diǎn)3、5，修改它們與白點(diǎn)相連的最小邊權(quán)。123452471162min[3]=w[2][3]=1;min[5]=w[2][5]=2;

第三次循環(huán)是找到min[3]最小的藍(lán)點(diǎn)3。將3變?yōu)榘c(diǎn)，接著枚舉與3相連的所有藍(lán)點(diǎn)4、5，修改它們與白點(diǎn)相連的最小邊權(quán)。

123452471162min[4]=w[3][4]=1;由于min[5]=2<w[3][5]=6;所以不修改min[5]的值。123452471162min[3]=w[2][3]=1;7最后兩輪循環(huán)將點(diǎn)4、5以及邊w[2][5],w[3][4]添加進(jìn)最小生成樹。123452471162最后權(quán)值之和MST=6。

這n次循環(huán)，每次循環(huán)我們都能讓一個(gè)新的點(diǎn)加入生成樹，n次循環(huán)就能把所有點(diǎn)囊括到其中；每次循環(huán)我們都能讓一條新的邊加入生成樹，n-1次循環(huán)就能生成一棵含有n個(gè)點(diǎn)的樹；每次循環(huán)我們都取一條最小的邊加入生成樹，n-1次循環(huán)結(jié)束后，我們得到的就是一棵最小的生成樹。這就是Prim采取貪心法生成一棵最小生成樹的原理。算法時(shí)間復(fù)雜度：O(N2)。123452471162最后權(quán)值之和MST=6。8算法描述：以1為起點(diǎn)生成最小生成樹，min[v]表示藍(lán)點(diǎn)v與白點(diǎn)相連的最小邊權(quán)。MST表示最小生成樹的權(quán)值之和。a）初始化：min[v]=∞(v≠1);min[1]=0;MST=0;b）for(i=1;i<=n;i++)1.尋找min[u]最小的藍(lán)點(diǎn)u。2.將u標(biāo)記為白點(diǎn)3.MST+=min[u]4.for與白點(diǎn)u相連的所有藍(lán)點(diǎn)vif(w[u][v]<min[v])min[v]=w[u][v];c）算法結(jié)束：MST即為最小生成樹的權(quán)值之和算法描述：9【例1】、最優(yōu)布線問題【問題描述】學(xué)校有n臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺(tái)計(jì)算機(jī)被連接是指它們間有數(shù)據(jù)線連接。由于計(jì)算機(jī)所處的位置不同，因此不同的兩臺(tái)計(jì)算機(jī)的連接費(fèi)用往往是不同的。當(dāng)然，如果將任意兩臺(tái)計(jì)算機(jī)都用數(shù)據(jù)線連接，費(fèi)用將是相當(dāng)龐大的。為了節(jié)省費(fèi)用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺(tái)計(jì)算機(jī)可以間接的通過若干臺(tái)計(jì)算機(jī)（作為中轉(zhuǎn)）來實(shí)現(xiàn)與另一臺(tái)計(jì)算機(jī)的連接?，F(xiàn)在由你負(fù)責(zé)連接這些計(jì)算機(jī)，任務(wù)是使任意兩臺(tái)計(jì)算機(jī)都連通（不管是直接的或間接的）?！据斎敫袷健枯斎胛募ire.in，第一行為整數(shù)n（2<=n<=100），表示計(jì)算機(jī)的數(shù)目。此后的n行，每行n個(gè)整數(shù)。第x+1行y列的整數(shù)表示直接連接第x臺(tái)計(jì)算機(jī)和第y臺(tái)計(jì)算機(jī)的費(fèi)用?！据敵龈袷健枯敵鑫募ire.out，一個(gè)整數(shù)，表示最小的連接費(fèi)用?！据斎霕永?012101210【輸出樣例】2（注：表示連接1和2，2和3，費(fèi)用為2）【例1】、最優(yōu)布線問題10【參考程序】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intg[101][101];//鄰接矩陣intminn[101];//minn[i]存放藍(lán)點(diǎn)i與白點(diǎn)相連的最小邊權(quán)boolu[101];//u[i]=True，表示頂點(diǎn)i還未加入到生成樹中//u[i]=False，表示頂點(diǎn)i已加入到生成樹中intn,i,j;intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>g[i][j];memset(minn,0x7f,sizeof(minn));//初始化為maxintminn[1]=0;memset(u,1,sizeof(u));//初始化為True，表示所有頂點(diǎn)為藍(lán)點(diǎn)【參考程序】11for(i=1;i<=n;i++){intk=0;for(j=1;j<=n;j++)//找一個(gè)與白點(diǎn)相連的權(quán)值最小的藍(lán)點(diǎn)kif(u[j]&&(minn[j]<minn[k]))k=j;u[k]=false;//藍(lán)點(diǎn)k加入生成樹，標(biāo)記為白點(diǎn)for(j=1;j<=n;j++)//修改與k相連的所有藍(lán)點(diǎn)if(u[j]&&(g[k][j]<minn[j]))minn[j]=g[k][j];}inttotal=0;for(i=1;i<=n;i++)//累加權(quán)值total+=minn[i];cout<<total<<endl;return0;}知識(shí)擴(kuò)展：本算法在移動(dòng)通信、智能交通、移動(dòng)物流、生產(chǎn)調(diào)度等物聯(lián)網(wǎng)相關(guān)領(lǐng)域都有十分現(xiàn)實(shí)的意義，采用好的算法，就能節(jié)省成本提高效率。for(i=1;i<=n;i++)12

【引例】有一張城市地圖，圖中的頂點(diǎn)為城市，無向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)特點(diǎn)，即任一對(duì)城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計(jì)可使得工程的總造價(jià)最少？12345212896731012345212896731013Kruskal算法Kruskal（克魯斯卡爾）算法是一種巧妙利用并查集來求最小生成樹的算法。

Kruskal算法將一個(gè)連通塊當(dāng)做一個(gè)集合。Kruskal首先將所有的邊按從小到大順序排序（一般使用快排），并認(rèn)為每一個(gè)點(diǎn)都是孤立的，分屬于n個(gè)獨(dú)立的集合。然后按順序枚舉每一條邊。如果這條邊連接著兩個(gè)不同的集合，那么就把這條邊加入最小生成樹，這兩個(gè)不同的集合就合并成了一個(gè)集合；如果這條邊連接的兩個(gè)點(diǎn)屬于同一集合，就跳過。直到選取了n-1條邊為止。123452128967310Kruskal算法Kruskal（克魯斯卡爾）算法是一種14思想講解：Kruskal（克魯斯卡爾）算法開始時(shí)，認(rèn)為每一個(gè)點(diǎn)都是孤立的，分屬于n個(gè)獨(dú)立的集合。1234521289673105個(gè)集合{{1}，{2}，{3}，{4}，{5}}生成樹中沒有邊Kruskal每次都選擇一條最小的邊，而且這條邊的兩個(gè)頂點(diǎn)分屬于兩個(gè)不同的集合。將選取的這條邊加入最小生成樹，并且合并集合。1234521289673105個(gè)集合{{1}，{2}，{15第一次選擇的是<1,2>這條邊，將這條邊加入到生成樹中，并且將它的兩個(gè)頂點(diǎn)1、2合并成一個(gè)集合。1234521289673104個(gè)集合{{1，2}，{3}，{4}，{5}}生成樹中有一條邊{<1,2>}第二次選擇的是<4,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個(gè)頂點(diǎn)4、5合并成一個(gè)集合。1234521289673103個(gè)集合{{1，2}，{3}，{4，5}}生成樹中有2條邊{<1,2>，<4,5>}第一次選擇的是<1,2>這條邊，將這條邊加入到生成樹中，并且16第三次選擇的是<3,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個(gè)頂點(diǎn)3、5所在的兩個(gè)集合合并成一個(gè)集合1234521289673102個(gè)集合{{1，2}，{3，4，5}}生成樹中有3條邊{<1,2>，<4,5>，<3，5>}第四次選擇的是<2,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個(gè)頂點(diǎn)2、5所在的兩個(gè)集合合并成一個(gè)集合。1234521289673101個(gè)集合{{1，2，3，4，5}}生成樹中有4條邊{<1,2>，<4,5>，<3，5>，<2,5>}第三次選擇的是<3,5>這條邊，將這條邊加入到生成樹中，并且17

算法結(jié)束，最小生成樹權(quán)值為19。通過上面的模擬能夠看到，Kruskal算法每次都選擇一條最小的，且能合并兩個(gè)不同集合的邊，一張n個(gè)點(diǎn)的圖總共選取n-1次邊。因?yàn)槊看挝覀冞x的都是最小的邊，所以最后的生成樹一定是最小生成樹。每次我們選的邊都能夠合并兩個(gè)集合，最后n個(gè)點(diǎn)一定會(huì)合并成一個(gè)集合。通過這樣的貪心策略，Kruskal算法就能得到一棵有n-1條邊，連接著n個(gè)點(diǎn)的最小生成樹。

Kruskal算法的時(shí)間復(fù)雜度為O(E*logE)，E為邊數(shù)。

18算法描述:初始化并查集。father[x]=x。tot=0將所有邊用快排從小到大排序。計(jì)數(shù)器k=0;for(i=1;i<=M;i++)//循環(huán)所有已從小到大排序的邊

if這是一條u,v不屬于同一集合的邊(u,v)(因?yàn)橐呀?jīng)排序，所以必為最小)

begin

①合并u,v所在的集合，相當(dāng)于把邊(u,v)加入最小生成樹。

②tot=tot+W(u,v)

③k++

④如果k=n-1,說明最小生成樹已經(jīng)生成，則break;end;6.結(jié)束，tot即為最小生成樹的總權(quán)值之和。算法描述:19【例2】、最短網(wǎng)絡(luò)Agri-Net【問題描述】農(nóng)民約翰被選為他們鎮(zhèn)的鎮(zhèn)長！他其中一個(gè)競選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場。當(dāng)然，他需要你的幫助。約翰已經(jīng)給他的農(nóng)場安排了一條高速的網(wǎng)絡(luò)線路，他想把這條線路共享給其他農(nóng)場。為了用最小的消費(fèi)，他想鋪設(shè)最短的光纖去連接所有的農(nóng)場。你將得到一份各農(nóng)場之間連接費(fèi)用的列表，你必須找出能連接所有農(nóng)場并所用光纖最短的方案。每兩個(gè)農(nóng)場間的距離不會(huì)超過100000?！据斎敫袷健康谝恍校恨r(nóng)場的個(gè)數(shù)，N（3<=N<=100）。第二行..結(jié)尾后來的行包含了一個(gè)N*N的矩陣,表示每個(gè)農(nóng)場之間的距離。理論上，他們是N行，每行由N個(gè)用空格分隔的數(shù)組成，實(shí)際上，他們限制在80個(gè)字符，因此，某些行會(huì)緊接著另一些行。當(dāng)然，對(duì)角線將會(huì)是0，因?yàn)椴粫?huì)有線路從第i個(gè)農(nóng)場到它本身。【輸出格式】

只有一個(gè)輸出，其中包含連接到每個(gè)農(nóng)場的光纖的最小長度。【輸入樣例】agrinet.in40492140817980162117160【輸出樣例】agrinet.out

28【例2】、最短網(wǎng)絡(luò)Agri-Net第一行：農(nóng)場的個(gè)數(shù)，20【參考程序】#include<cstdio>#include<iostream>#include<algorithm>//sort()需要用到<algorithm>庫usingnamespacestd;structpoint{intx;inty;intv;};

//定義結(jié)構(gòu)類型，表示邊pointa[9901];

//存邊intfat[101];intn,i,j,x,m,tot,k;intfather(intx){if(fat[x]!=x)fat[x]=father(fat[x]);returnfat[x];}voidunionn(intx,inty){intfa=father(x);intfb=father(y);if(fa!=fb)fat[fa]=fb;}【參考程序】21intcmp(constpoint&a,constpoint&b)//sort()自定義的比較函數(shù){if(a.v<b.v)return1;elsereturn0;}intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>x;if(x!=0){m++;a[m].x=i;a[m].y=j;a[m].v=x;}}for(i=1;i<=n;i++)fat[i]=i;sort(a+1,a+m+1,cmp);//C++標(biāo)準(zhǔn)庫中自帶的快排

//cmp為自定義的比較函數(shù)。表示a數(shù)組的1-m按規(guī)則cmp排序intcmp(constpoint&a,constp22for(i=1;i<=m;i++){if(father(a[i].x)!=father(a[i].y)){unionn(a[i].x,a[i].y);tot+=a[i].v;k++;}if(k==n-1)break;}cout<<tot;return0;}最小生成樹和拓?fù)渑判蛘n件23上機(jī)練習(xí)1、局域網(wǎng)【問題描述】某個(gè)局域網(wǎng)內(nèi)有n(n<=100)臺(tái)計(jì)算機(jī)，由于搭建局域網(wǎng)時(shí)工作人員的疏忽，現(xiàn)在局域網(wǎng)內(nèi)的連接形成了回路，我們知道如果局域網(wǎng)形成回路那么數(shù)據(jù)將不停的在回路內(nèi)傳輸，造成網(wǎng)絡(luò)卡的現(xiàn)象。因?yàn)檫B接計(jì)算機(jī)的網(wǎng)線本身不同，所以有一些連線不是很暢通，我們用f(i,j)表示i,j之間連接的暢通程度(f(i,j)<=1000)，f(i,j)值越小表示i,j之間連接越通暢，f(i,j)為0表示i,j之間無網(wǎng)線連接?，F(xiàn)在我們需要解決回路問題，我們將除去一些連線，使得網(wǎng)絡(luò)中沒有回路，并且被除去網(wǎng)線的Σf(i,j)最大，請(qǐng)求出這個(gè)最大值?！据斎敫袷健康谝恍袃蓚€(gè)正整數(shù)nk接下來的k行每行三個(gè)正整數(shù)ijm表示i,j兩臺(tái)計(jì)算機(jī)之間有網(wǎng)線聯(lián)通，通暢程度為m。【輸出格式】一個(gè)正整數(shù)，Σf(i,j)的最大值【輸入輸出樣例】【輸入樣例】【輸出樣例】551281311532453428上機(jī)練習(xí)1、局域網(wǎng)【輸入樣例】【輸出樣例】5515242、繁忙的都市【問題描述】城市C是一個(gè)非常繁忙的大都市，城市中的道路十分的擁擠，于是市長決定對(duì)其中的道路進(jìn)行改造。城市C的道路是這樣分布的：城市中有n個(gè)交叉路口，有些交叉路口之間有道路相連，兩個(gè)交叉路口之間最多有一條道路相連接。這些道路是雙向的，且把所有的交叉路口直接或間接的連接起來了。每條道路都有一個(gè)分值，分值越小表示這個(gè)道路越繁忙，越需要進(jìn)行改造。但是市政府的資金有限，市長希望進(jìn)行改造的道路越少越好，于是他提出下面的要求：改造的那些道路能夠把所有的交叉路口直接或間接的連通起來。在滿足要求1的情況下，改造的道路盡量少。在滿足要求1、2的情況下，改造的那些道路中分值最大值盡量小。【編程任務(wù)】作為市規(guī)劃局的你，應(yīng)當(dāng)作出最佳的決策，選擇那些道路應(yīng)當(dāng)被修建?！据斎敫袷健縞ity.in第一行有兩個(gè)整數(shù)n,m表示城市有n個(gè)交叉路口，m條道路。接下來m行是對(duì)每條道路的描述，u,v,c表示交叉路口u和v之間有道路相連，分值為c。(1≤n≤300，1≤c≤10000)【輸出格式】city.out兩個(gè)整數(shù)s,max，表示你選出了幾條道路，分值最大的那條道路的分值是多少?！据斎胼敵鰳永俊据斎霕永俊据敵鰳永?5123145247236348362、繁忙的都市【輸入樣例】【輸出樣例】452363253、聯(lián)絡(luò)員【問題描述】

Tyvj已經(jīng)一歲了，網(wǎng)站也由最初的幾個(gè)用戶增加到了上萬個(gè)用戶，隨著Tyvj網(wǎng)站的逐步壯大，管理員的數(shù)目也越來越多，現(xiàn)在你身為Tyvj管理層的聯(lián)絡(luò)員，希望你找到一些通信渠道，使得管理員兩兩都可以聯(lián)絡(luò)（直接或者是間接都可以）。Tyvj是一個(gè)公益性的網(wǎng)站，沒有過多的利潤，所以你要盡可能的使費(fèi)用少才可以。目前你已經(jīng)知道，Tyvj的通信渠道分為兩大類，一類是必選通信渠道，無論價(jià)格多少，你都需要把所有的都選擇上；還有一類是選擇性的通信渠道，你可以從中挑選一些作為最終管理員聯(lián)絡(luò)的通信渠道。數(shù)據(jù)保證給出的通行渠道可以讓所有的管理員聯(lián)通?！据斎敫袷健?/p>

第一行n，m表示Tyvj一共有n個(gè)管理員，有m個(gè)通信渠道第二行到m+1行，每行四個(gè)非負(fù)整數(shù)，p,u,v,w當(dāng)p=1時(shí)，表示這個(gè)通信渠道為必選通信渠道；當(dāng)p=2時(shí)，表示這個(gè)通信渠道為選擇性通信渠道；u,v,w表示本條信息描述的是u，v管理員之間的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示費(fèi)用?！据敵龈袷健?/p>

最小的通信費(fèi)用。3、聯(lián)絡(luò)員26561121123113411411225102255【輸入樣例】【輸出樣例】9樣例解釋：1-2-3-4-1存在四個(gè)必選渠道，形成一個(gè)環(huán)，互相可以到達(dá)。需要讓所有管理員聯(lián)通，需要聯(lián)通2和5號(hào)管理員，選擇費(fèi)用為5的渠道，所以總的費(fèi)用為9注意：u,v之間可能存在多條通信渠道，你的程序應(yīng)該累加所有u,v之間的必選通行渠道數(shù)據(jù)范圍：對(duì)于30%的數(shù)據(jù)，n<=10m<=100對(duì)于50%的數(shù)據(jù),n<=200m<=1000對(duì)于100%的數(shù)據(jù)，n<=2000m<=1000056【輸入樣例】【輸出樣例】樣例解釋：27拓?fù)渑判蛲負(fù)渑判?8AOV網(wǎng)

在日常生活中，一項(xiàng)大的工程可以看作是由若干個(gè)子工程（這些子工程稱為“活動(dòng)”）組成的集合，這些子工程（活動(dòng)）之間必定存在一些先后關(guān)系，即某些子工程（活動(dòng)）必須在其它一些子工程（活動(dòng)）完成之后才能開始，我們可以用有向圖來形象地表示這些子工程（活動(dòng)）之間的先后關(guān)系，子工程（活動(dòng)）為頂點(diǎn)，子工程（活動(dòng)）之間的先后關(guān)系為有向邊，這種有向圖稱為“頂點(diǎn)活動(dòng)網(wǎng)絡(luò)”，又稱“AOV網(wǎng)”。123567894AOV網(wǎng)12356789429在AOV網(wǎng)中，有向邊代表子工程（活動(dòng)）的先后關(guān)系，我們把一條有向邊起點(diǎn)的活動(dòng)成為終點(diǎn)活動(dòng)的前驅(qū)活動(dòng)，同理終點(diǎn)的活動(dòng)稱為起點(diǎn)活動(dòng)的后繼活動(dòng)。而只有當(dāng)一個(gè)活動(dòng)全部的前驅(qū)全部都完成之后，這個(gè)活動(dòng)才能進(jìn)行。例如在上圖中，只有當(dāng)工程1完成之后，工程2、3、4、5、6才能開始進(jìn)行。只有當(dāng)2、3、4全部完成之后，7才能開始進(jìn)行。一個(gè)AOV網(wǎng)必定是一個(gè)有向無環(huán)圖，即不應(yīng)該帶有回路。否則，會(huì)出現(xiàn)先后關(guān)系的自相矛盾。1234上圖就是一個(gè)出現(xiàn)環(huán)產(chǎn)生自相矛盾的情況。4是1的前驅(qū)，想完成1，必須先完成4。3是4的前驅(qū)，而2是3的前驅(qū)，1又是2的前驅(qū)。最后造成想完成1，必須先完成1本身，這顯然出現(xiàn)了矛盾。在AOV網(wǎng)中，有向邊代表子工程（活動(dòng)）的先后關(guān)系，我們把30拓?fù)渑判蛩惴?/p>

拓?fù)渑判蛩惴ǎ贿m用于AOV網(wǎng)（有向無環(huán)圖）。把AOV網(wǎng)中的所有活動(dòng)排成一個(gè)序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，這個(gè)過程稱為“拓?fù)渑判颉?，所得到的活?dòng)序列稱為“拓?fù)湫蛄小薄Ｒ粋€(gè)AOV網(wǎng)的拓?fù)湫蛄惺遣晃ㄒ坏?，例如下面的這張圖，它的拓?fù)湫蛄锌梢允牵篈BCDE，也可以是ACBDE，或是ADBCE。在下圖所示的AOV網(wǎng)中，工程B和工程C顯然可以同時(shí)進(jìn)行，先后無所謂；但工程E卻要等工程B、C、D都完成以后才能進(jìn)行。ABCED

構(gòu)造拓?fù)湫蛄锌梢詭椭覀兒侠戆才乓粋€(gè)工程的進(jìn)度，由AOV網(wǎng)構(gòu)造拓?fù)湫蛄芯哂泻芨叩膶?shí)際應(yīng)用價(jià)值。拓?fù)渑判蛩惴ㄍ負(fù)渑判蛩惴?，只適用于AOV網(wǎng)（有向無31算法思想：構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄋ枷牒芎唵危?）選擇一個(gè)入度為0的頂點(diǎn)并輸出2）然后從AOV網(wǎng)中刪除此頂點(diǎn)及以此頂點(diǎn)為起點(diǎn)的所有關(guān)聯(lián)邊；3）重復(fù)上述兩步，直到不存在入度為0的頂點(diǎn)為止。4）若輸出的頂點(diǎn)數(shù)小于AOV網(wǎng)中的頂點(diǎn)數(shù)，則輸出“有回路信息”，否則輸出的頂點(diǎn)序列就是一種拓?fù)湫蛄袕牡谒牟娇梢钥闯?，拓?fù)渑判蚩梢杂脕砼袛嘁粋€(gè)有向圖是否有環(huán)。只有有向無環(huán)圖才存在拓?fù)湫蛄小Ｗ钚∩蓸浜屯負(fù)渑判蛘n件32算法實(shí)現(xiàn)：a)數(shù)據(jù)結(jié)構(gòu)：indgr[i]:

頂點(diǎn)i的入度;

stack[

]:

棧b)初始化:top=0(棧頂指針置零)c)將初始狀態(tài)所有入度為0的頂點(diǎn)壓棧d)I=0(計(jì)數(shù)器)e)while棧非空(top>0)i.棧頂?shù)捻旤c(diǎn)v出棧；top-1;輸出v；i++；ii.forv的每一個(gè)后繼頂點(diǎn)u1.indgr[u]--;u的入度減12.if（u的入度變?yōu)?）頂點(diǎn)u入棧f)算法結(jié)束這個(gè)程序采用棧來找出入度為0的點(diǎn)，棧里的頂點(diǎn)，都是入度為0的點(diǎn)。算法實(shí)現(xiàn)：33我們結(jié)合下圖詳細(xì)講解：ABCD開始時(shí)，只有A入度為0，A入棧。棧：ABCD棧頂元素A出棧并輸出A，A的后繼B、C入度減1，相當(dāng)于刪除A的所有關(guān)聯(lián)邊棧：空拓?fù)湫蛄校篈我們結(jié)合下圖詳細(xì)講解：ABCD開始時(shí)，只有A入度為0，A入棧34BCDB、C的入度都變成0，依次將B、C入棧。棧：BC（入棧順序不唯一）拓?fù)湫蛄校篈BD棧頂元素C出棧并輸出C，C的后繼D入度減1棧：B拓?fù)湫蛄校篈CBCDB、C的入度都變成0，依次將B、C入棧。棧：BC（入棧35D棧頂元素B出棧并輸出B，B的后繼D入度再減1。這時(shí)D入度為0，入棧。棧：D拓?fù)湫蛄校篈CBD棧頂元素D出棧并輸出D。棧空，結(jié)束棧：空拓?fù)湫蛄校篈CBD（不唯一）簡單&高效&實(shí)用的算法。上述實(shí)現(xiàn)方法復(fù)雜度O(V+E)。D棧頂元素B出棧并輸出B，B的后繼D入度再減1。這時(shí)D入度為36【例3】、家譜樹【問題描述】有個(gè)人的家族很大，輩分關(guān)系很混亂，請(qǐng)你幫整理一下這種關(guān)系。給出每個(gè)人的孩子的信息。輸出一個(gè)序列，使得每個(gè)人的后輩都比那個(gè)人后列出。【輸入格式】第1行一個(gè)整數(shù)N（1<=N<=100），表示家族的人數(shù)。接下來N行，第I行描述第I個(gè)人的兒子。每行最后是0表示描述完畢?！据敵龈袷健枯敵鲆粋€(gè)序列，使得每個(gè)人的后輩都比那個(gè)人后列出。如果有多解輸出任意一解?！据斎霕永?/p>

5045101053030【輸出樣例】

24531最小生成樹和拓?fù)渑判蛘n件37【參考程序】#include<cstdio>#include<iostream>usingnamespacestd;inta[101][101],c[101],r[101],ans[101];inti,j,tot,temp,num,n,m;intmain(){cin>>n;for(i=1;i<=n;i++){do{cin>>j;if(j!=0){c[i]++;//c[i]用來存點(diǎn)i的出度a[i][c[i]]=j;r[j]++;//a[i,-1]用來存點(diǎn)i的入度。}}while(j!=0);}【參考程序】38for(i=1;i<=n;i++)if(r[i]==0)ans[++tot]=i;

//把圖中所有入度為0的點(diǎn)入棧，棧用一維數(shù)組ans[]表示do{temp=ans[tot];cout<<temp<<"";tot--;num++;

//棧頂元素出棧并輸出for(i=1;i<=c[temp];i++){r[a[temp][i]]--;if(r[a[temp][i]]==0)//如果入度減1后變成0，則將這個(gè)后繼點(diǎn)入棧ans[++tot]=a[temp][i];}}while(num!=n);

//如果輸出的點(diǎn)的數(shù)目num等于n，說明算法結(jié)束return0;}for(i=1;i<=n;i++)39【例4】獎(jiǎng)金【問題描述】由于無敵的凡凡在2005年世界英俊帥氣男總決選中勝出，YaliCompany總經(jīng)理Mr.Z心情好，決定給每位員工發(fā)獎(jiǎng)金。公司決定以每個(gè)人本年在公司的貢獻(xiàn)為標(biāo)準(zhǔn)來計(jì)算他們得到獎(jiǎng)金的多少。于是Mr.Z下令召開m方會(huì)談。每位參加會(huì)談的代表提出了自己的意見：“我認(rèn)為員工a的獎(jiǎng)金應(yīng)該比b高！”Mr.Z決定要找出一種獎(jiǎng)金方案，滿足各位代表的意見，且同時(shí)使得總獎(jiǎng)金數(shù)最少。每位員工獎(jiǎng)金最少為100元?！据斎敫袷健康谝恍袃蓚€(gè)整數(shù)n,m，表示員工總數(shù)和代表數(shù)；以下m行，每行2個(gè)整數(shù)a,b，表示某個(gè)代表認(rèn)為第a號(hào)員工獎(jiǎng)金應(yīng)該比第b號(hào)員工高?！据敵龈袷健咳魺o法找到合理方案，則輸出“PoorXed”；否則輸出一個(gè)數(shù)表示最少總獎(jiǎng)金?！据斎霕永?/p>

21

12【輸出樣例】

201最小生成樹和拓?fù)渑判蛘n件40【數(shù)據(jù)規(guī)模】

80％的數(shù)據(jù)滿足n<=1000，m<=2000；100％的數(shù)據(jù)滿足n<=10000，m<=20000?！舅惴ǚ治觥渴紫葮?gòu)圖，若存在條件“a的錢比b多”則從b引一條有向指向a；然后拓?fù)渑判?，若無法完成排序則表示問題無解（存在圈）；若可以得到完整的拓?fù)湫蛄?，則按序列順序進(jìn)行遞推：設(shè)f[i]表示第i個(gè)人能拿的最少獎(jiǎng)金數(shù)；首先所有f[i]=100（題目中給定的最小值）；然后按照拓?fù)漤樞蚩疾烀總€(gè)點(diǎn)i，若存在有向邊(j,i)，則表示f[i]必須比f[j]大，因此我們令f[i]=Max{f[i],f[j]+1}即可；遞推完成之后所有f[i]的值也就確定了，而答案就等于f[1]+…+f[n]。最小生成樹和拓?fù)渑判蛘n件41【參考程序】#include<iostream>usingnamespacestd;inta[10001][301]={0},into[10001],ans[10001],m,n,money;voidinit()

//讀入數(shù)據(jù)，并構(gòu)建圖，統(tǒng)計(jì)入度{inti,x,y;cin>>n>>m;for(i=1;i<=m;i++){cin>>x>>y;a[y][0]++;

//記錄由y引出邊的數(shù)目a[y][a[y][0]]=x;//記錄由a[y][0]引出邊的頂點(diǎn)into[x]++;//統(tǒng)計(jì)入度}}booltopsort()//拓?fù)渑判騵intt,tot,k,i,j;tot=0;k=0;while(tot<n)//tot頂點(diǎn)個(gè)數(shù){t=0;

//用來判斷有無環(huán)for(i=1;i<=n;i++)if(into[i]==0)

【參考程序】42{tot++;t++;money+=100;ans[t]=i;into[i]=0xfffffff;}if(t==0)returnfalse;//存在環(huán)

money+=k*t;k++;for(i=1;i<=t;i++)//去掉相連的邊

for(j=1;j<=a[ans[i]][0];j++)into[a[ans[i]][j]]--;}returntrue;}intmain(){init();money=0;if(topsort())cout<<money<<endl;elsecout<<"PoorXed"<<endl;return0;}{43上機(jī)練習(xí)4、煩人的幻燈片【問題描述】李教授將于今天下午作一次非常重要的演講。不信的事他不是一個(gè)非常愛整潔的人，他把自己演講要用的幻燈片隨便堆在了一起。因此，演講之前他不得不去整理這些幻燈片。作為一個(gè)講求效率的學(xué)者，他希望盡可能簡單地完成它。教授這次演講一共要用n張幻燈片（n<=26），這n張幻燈片按照演講要使用的順序已經(jīng)用數(shù)字1~n編了號(hào)。因?yàn)榛脽羝峭该鞯?，所以我們不能一下子看清每一個(gè)數(shù)字所對(duì)應(yīng)的幻燈片?，F(xiàn)在我們用大寫字母A,B,C……再次把幻燈片依次編號(hào)。你的任務(wù)是編寫一個(gè)程序，把幻燈片的數(shù)字編號(hào)和字母編號(hào)對(duì)應(yīng)起來，顯然這種對(duì)應(yīng)應(yīng)該是唯一的；若出現(xiàn)多種對(duì)應(yīng)的情況或是某些數(shù)字編號(hào)和字母編號(hào)對(duì)應(yīng)不起來，我們稱對(duì)應(yīng)是無法實(shí)現(xiàn)的?！据斎敫袷健课募牡谝恍兄挥幸粋€(gè)整數(shù)n，表示有n張幻燈片，接下來的n行每行包括4個(gè)整數(shù)xmin,xmax,ymin,ymax（整數(shù)之間用空格分開）為幻燈片的坐標(biāo)，這n張幻燈片按其在文件中出現(xiàn)的順序從前到后依次編號(hào)為A,B,C……，再接下來的n行依次為n個(gè)數(shù)字編號(hào)的坐標(biāo)x,y，顯然在幻燈片之外是不會(huì)有數(shù)字的?！据敵龈袷健咳羰菍?duì)應(yīng)可以實(shí)現(xiàn)，輸出文件應(yīng)該包括n行，每一行為一個(gè)字母和一個(gè)數(shù)字，中間以一個(gè)空格隔開，并且每行以字母的升序排列，注意輸出的字母要大寫并且定格；反之，若是對(duì)應(yīng)無法實(shí)現(xiàn)，在文件的第一行頂格輸出None即可。首行末無多余的空格。上機(jī)練習(xí)4、煩人的幻燈片44上機(jī)練習(xí)【輸入輸出樣例】slides.inslides.out4622102041861682021810244891519171172111A4B1C2D3上機(jī)練習(xí)slides.inslides.out4A4455、病毒【問題描述】有一天，小y突然發(fā)現(xiàn)自己的計(jì)算機(jī)感染了一種病毒！還好，小y發(fā)現(xiàn)這種病毒很弱，只是會(huì)把文檔中的所有字母替換成其它字母，但并不改變順序，也不會(huì)增加和刪除字母?，F(xiàn)在怎么恢復(fù)原來的文檔呢！小y很聰明，他在其他沒有感染病毒的機(jī)器上，生成了一個(gè)由若干單詞構(gòu)成的字典，字典中的單詞是按照字母順序排列的，他把這個(gè)文件拷貝到自己的機(jī)器里，故意讓它感染上病毒，他想利用這個(gè)字典文件原來的有序性，找到病毒替換字母的規(guī)律，再用來恢復(fù)其它文檔?，F(xiàn)在你的任務(wù)是：告訴你被病毒感染了的字典，要你恢復(fù)一個(gè)字母串?！据斎敫袷健縱irus.in第一行為整數(shù)K（≤50000），表示字典中的單詞個(gè)數(shù)。以下K行，是被病毒感染了的字典，每行一個(gè)單詞。最后一行是需要你恢復(fù)的一串字母。所有字母均為小寫?！据敵龈袷健縱irus.out輸出僅一行，為恢復(fù)后的一串字母。當(dāng)然也有可能出現(xiàn)字典不完整、甚至字典是錯(cuò)的情況，這時(shí)請(qǐng)輸出一個(gè)0。最小生成樹和拓?fù)渑判蛘n件46【輸入樣例】

6

cebdbac

cac

ecd

dca

aba

bac

cedab【輸出樣例】

abcde【輸入樣例】47最小生成樹和7月18日最小生成樹和7月18日48最小生成樹最小生成樹49一、什么是圖的最小生成樹（MST）？

不知道大家還記不記得樹的一個(gè)定理：N個(gè)點(diǎn)用N-1條邊連接成一個(gè)連通塊，形成的圖形只可能是樹，沒有別的可能。

一個(gè)有N個(gè)點(diǎn)的圖，邊一定是大于等于N-1條的。圖的最小生成樹，就是在這些邊中選擇N-1條出來，連接所有的N個(gè)點(diǎn)。這N-1條邊的邊權(quán)之和是所有方案中最小的。一、什么是圖的最小生成樹（MST）？一個(gè)有N個(gè)點(diǎn)的圖，50二、最小生成樹用來解決什么問題？

就是用來解決如何用最小的“代價(jià)”用N-1條邊連接N個(gè)點(diǎn)的問題?！疽坑幸粡埑鞘械貓D，圖中的頂點(diǎn)為城市，無向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)特點(diǎn)，即任一對(duì)城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計(jì)可使得工程的總造價(jià)最少？123452471162二、最小生成樹用來解決什么問題？就是用來解決如何用最51Prim算法算法分析&思想講解：Prim算法采用“藍(lán)白點(diǎn)”思想：白點(diǎn)代表已經(jīng)進(jìn)入最小生成樹的點(diǎn)，藍(lán)點(diǎn)代表未進(jìn)入最小生成樹的點(diǎn)。Prim算法每次循環(huán)都將一個(gè)藍(lán)點(diǎn)u變?yōu)榘c(diǎn)，并且此藍(lán)點(diǎn)u與白點(diǎn)相連的最小邊權(quán)min[u]還是當(dāng)前所有藍(lán)點(diǎn)中最小的。這樣相當(dāng)于向生成樹中添加了n-1次最小的邊，最后得到的一定是最小生成樹。我們通過對(duì)右圖最小生成樹的求解模擬來理解上面的思想。藍(lán)點(diǎn)和虛線代表未進(jìn)入最小生成樹的點(diǎn)、邊；白點(diǎn)和實(shí)線代表已進(jìn)入最小生成樹的點(diǎn)、邊。123452471162Prim算法算法分析&思想講解：12345247116252初始時(shí)所有點(diǎn)都是藍(lán)點(diǎn)，min[1]=0,min[2、3、4、5]=∞。權(quán)值之和MST=0。123452471162第一次循環(huán)自然是找到min[1]=0最小的藍(lán)點(diǎn)1。將1變?yōu)榘c(diǎn)，接著枚舉與1相連的所有藍(lán)點(diǎn)2、3、4，修改它們與白點(diǎn)相連的最小邊權(quán)。123452471162min[2]=w[1][2]=2;min[3]=w[1][3]=4;min[4]=w[1][4]=7;123452471162第一次循環(huán)自然是找到min[1]=053第二次循環(huán)是找到min[2]最小的藍(lán)點(diǎn)2。將2變?yōu)榘c(diǎn)，接著枚舉與2相連的所有藍(lán)點(diǎn)3、5，修改它們與白點(diǎn)相連的最小邊權(quán)。123452471162min[3]=w[2][3]=1;min[5]=w[2][5]=2;

第三次循環(huán)是找到min[3]最小的藍(lán)點(diǎn)3。將3變?yōu)榘c(diǎn)，接著枚舉與3相連的所有藍(lán)點(diǎn)4、5，修改它們與白點(diǎn)相連的最小邊權(quán)。

123452471162min[4]=w[3][4]=1;由于min[5]=2<w[3][5]=6;所以不修改min[5]的值。123452471162min[3]=w[2][3]=1;54最后兩輪循環(huán)將點(diǎn)4、5以及邊w[2][5],w[3][4]添加進(jìn)最小生成樹。123452471162最后權(quán)值之和MST=6。

這n次循環(huán)，每次循環(huán)我們都能讓一個(gè)新的點(diǎn)加入生成樹，n次循環(huán)就能把所有點(diǎn)囊括到其中；每次循環(huán)我們都能讓一條新的邊加入生成樹，n-1次循環(huán)就能生成一棵含有n個(gè)點(diǎn)的樹；每次循環(huán)我們都取一條最小的邊加入生成樹，n-1次循環(huán)結(jié)束后，我們得到的就是一棵最小的生成樹。這就是Prim采取貪心法生成一棵最小生成樹的原理。算法時(shí)間復(fù)雜度：O(N2)。123452471162最后權(quán)值之和MST=6。55算法描述：以1為起點(diǎn)生成最小生成樹，min[v]表示藍(lán)點(diǎn)v與白點(diǎn)相連的最小邊權(quán)。MST表示最小生成樹的權(quán)值之和。a）初始化：min[v]=∞(v≠1);min[1]=0;MST=0;b）for(i=1;i<=n;i++)1.尋找min[u]最小的藍(lán)點(diǎn)u。2.將u標(biāo)記為白點(diǎn)3.MST+=min[u]4.for與白點(diǎn)u相連的所有藍(lán)點(diǎn)vif(w[u][v]<min[v])min[v]=w[u][v];c）算法結(jié)束：MST即為最小生成樹的權(quán)值之和算法描述：56【例1】、最優(yōu)布線問題【問題描述】學(xué)校有n臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺(tái)計(jì)算機(jī)被連接是指它們間有數(shù)據(jù)線連接。由于計(jì)算機(jī)所處的位置不同，因此不同的兩臺(tái)計(jì)算機(jī)的連接費(fèi)用往往是不同的。當(dāng)然，如果將任意兩臺(tái)計(jì)算機(jī)都用數(shù)據(jù)線連接，費(fèi)用將是相當(dāng)龐大的。為了節(jié)省費(fèi)用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺(tái)計(jì)算機(jī)可以間接的通過若干臺(tái)計(jì)算機(jī)（作為中轉(zhuǎn)）來實(shí)現(xiàn)與另一臺(tái)計(jì)算機(jī)的連接?，F(xiàn)在由你負(fù)責(zé)連接這些計(jì)算機(jī)，任務(wù)是使任意兩臺(tái)計(jì)算機(jī)都連通（不管是直接的或間接的）。【輸入格式】輸入文件wire.in，第一行為整數(shù)n（2<=n<=100），表示計(jì)算機(jī)的數(shù)目。此后的n行，每行n個(gè)整數(shù)。第x+1行y列的整數(shù)表示直接連接第x臺(tái)計(jì)算機(jī)和第y臺(tái)計(jì)算機(jī)的費(fèi)用?！据敵龈袷健枯敵鑫募ire.out，一個(gè)整數(shù)，表示最小的連接費(fèi)用?！据斎霕永?012101210【輸出樣例】2（注：表示連接1和2，2和3，費(fèi)用為2）【例1】、最優(yōu)布線問題57【參考程序】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intg[101][101];//鄰接矩陣intminn[101];//minn[i]存放藍(lán)點(diǎn)i與白點(diǎn)相連的最小邊權(quán)boolu[101];//u[i]=True，表示頂點(diǎn)i還未加入到生成樹中//u[i]=False，表示頂點(diǎn)i已加入到生成樹中intn,i,j;intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>g[i][j];memset(minn,0x7f,sizeof(minn));//初始化為maxintminn[1]=0;memset(u,1,sizeof(u));//初始化為True，表示所有頂點(diǎn)為藍(lán)點(diǎn)【參考程序】58for(i=1;i<=n;i++){intk=0;for(j=1;j<=n;j++)//找一個(gè)與白點(diǎn)相連的權(quán)值最小的藍(lán)點(diǎn)kif(u[j]&&(minn[j]<minn[k]))k=j;u[k]=false;//藍(lán)點(diǎn)k加入生成樹，標(biāo)記為白點(diǎn)for(j=1;j<=n;j++)//修改與k相連的所有藍(lán)點(diǎn)if(u[j]&&(g[k][j]<minn[j]))minn[j]=g[k][j];}inttotal=0;for(i=1;i<=n;i++)//累加權(quán)值total+=minn[i];cout<<total<<endl;return0;}知識(shí)擴(kuò)展：本算法在移動(dòng)通信、智能交通、移動(dòng)物流、生產(chǎn)調(diào)度等物聯(lián)網(wǎng)相關(guān)領(lǐng)域都有十分現(xiàn)實(shí)的意義，采用好的算法，就能節(jié)省成本提高效率。for(i=1;i<=n;i++)59

【引例】有一張城市地圖，圖中的頂點(diǎn)為城市，無向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)特點(diǎn)，即任一對(duì)城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計(jì)可使得工程的總造價(jià)最少？12345212896731012345212896731060Kruskal算法Kruskal（克魯斯卡爾）算法是一種巧妙利用并查集來求最小生成樹的算法。

Kruskal算法將一個(gè)連通塊當(dāng)做一個(gè)集合。Kruskal首先將所有的邊按從小到大順序排序（一般使用快排），并認(rèn)為每一個(gè)點(diǎn)都是孤立的，分屬于n個(gè)獨(dú)立的集合。然后按順序枚舉每一條邊。如果這條邊連接著兩個(gè)不同的集合，那么就把這條邊加入最小生成樹，這兩個(gè)不同的集合就合并成了一個(gè)集合；如果這條邊連接的兩個(gè)點(diǎn)屬于同一集合，就跳過。直到選取了n-1條邊為止。123452128967310Kruskal算法Kruskal（克魯斯卡爾）算法是一種61思想講解：Kruskal（克魯斯卡爾）算法開始時(shí)，認(rèn)為每一個(gè)點(diǎn)都是孤立的，分屬于n個(gè)獨(dú)立的集合。1234521289673105個(gè)集合{{1}，{2}，{3}，{4}，{5}}生成樹中沒有邊Kruskal每次都選擇一條最小的邊，而且這條邊的兩個(gè)頂點(diǎn)分屬于兩個(gè)不同的集合。將選取的這條邊加入最小生成樹，并且合并集合。1234521289673105個(gè)集合{{1}，{2}，{62第一次選擇的是<1,2>這條邊，將這條邊加入到生成樹中，并且將它的兩個(gè)頂點(diǎn)1、2合并成一個(gè)集合。1234521289673104個(gè)集合{{1，2}，{3}，{4}，{5}}生成樹中有一條邊{<1,2>}第二次選擇的是<4,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個(gè)頂點(diǎn)4、5合并成一個(gè)集合。1234521289673103個(gè)集合{{1，2}，{3}，{4，5}}生成樹中有2條邊{<1,2>，<4,5>}第一次選擇的是<1,2>這條邊，將這條邊加入到生成樹中，并且63第三次選擇的是<3,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個(gè)頂點(diǎn)3、5所在的兩個(gè)集合合并成一個(gè)集合1234521289673102個(gè)集合{{1，2}，{3，4，5}}生成樹中有3條邊{<1,2>，<4,5>，<3，5>}第四次選擇的是<2,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個(gè)頂點(diǎn)2、5所在的兩個(gè)集合合并成一個(gè)集合。1234521289673101個(gè)集合{{1，2，3，4，5}}生成樹中有4條邊{<1,2>，<4,5>，<3，5>，<2,5>}第三次選擇的是<3,5>這條邊，將這條邊加入到生成樹中，并且64

算法結(jié)束，最小生成樹權(quán)值為19。通過上面的模擬能夠看到，Kruskal算法每次都選擇一條最小的，且能合并兩個(gè)不同集合的邊，一張n個(gè)點(diǎn)的圖總共選取n-1次邊。因?yàn)槊看挝覀冞x的都是最小的邊，所以最后的生成樹一定是最小生成樹。每次我們選的邊都能夠合并兩個(gè)集合，最后n個(gè)點(diǎn)一定會(huì)合并成一個(gè)集合。通過這樣的貪心策略，Kruskal算法就能得到一棵有n-1條邊，連接著n個(gè)點(diǎn)的最小生成樹。

Kruskal算法的時(shí)間復(fù)雜度為O(E*logE)，E為邊數(shù)。

65算法描述:初始化并查集。father[x]=x。tot=0將所有邊用快排從小到大排序。計(jì)數(shù)器k=0;for(i=1;i<=M;i++)//循環(huán)所有已從小到大排序的邊

if這是一條u,v不屬于同一集合的邊(u,v)(因?yàn)橐呀?jīng)排序，所以必為最小)

begin

①合并u,v所在的集合，相當(dāng)于把邊(u,v)加入最小生成樹。

②tot=tot+W(u,v)

③k++

④如果k=n-1,說明最小生成樹已經(jīng)生成，則break;end;6.結(jié)束，tot即為最小生成樹的總權(quán)值之和。算法描述:66【例2】、最短網(wǎng)絡(luò)Agri-Net【問題描述】農(nóng)民約翰被選為他們鎮(zhèn)的鎮(zhèn)長！他其中一個(gè)競選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場。當(dāng)然，他需要你的幫助。約翰已經(jīng)給他的農(nóng)場安排了一條高速的網(wǎng)絡(luò)線路，他想把這條線路共享給其他農(nóng)場。為了用最小的消費(fèi)，他想鋪設(shè)最短的光纖去連接所有的農(nóng)場。你將得到一份各農(nóng)場之間連接費(fèi)用的列表，你必須找出能連接所有農(nóng)場并所用光纖最短的方案。每兩個(gè)農(nóng)場間的距離不會(huì)超過100000?！据斎敫袷健康谝恍校恨r(nóng)場的個(gè)數(shù)，N（3<=N<=100）。第二行..結(jié)尾后來的行包含了一個(gè)N*N的矩陣,表示每個(gè)農(nóng)場之間的距離。理論上，他們是N行，每行由N個(gè)用空格分隔的數(shù)組成，實(shí)際上，他們限制在80個(gè)字符，因此，某些行會(huì)緊接著另一些行。當(dāng)然，對(duì)角線將會(huì)是0，因?yàn)椴粫?huì)有線路從第i個(gè)農(nóng)場到它本身?！据敵龈袷健?/p>

只有一個(gè)輸出，其中包含連接到每個(gè)農(nóng)場的光纖的最小長度?！据斎霕永縜grinet.in40492140817980162117160【輸出樣例】agrinet.out

28【例2】、最短網(wǎng)絡(luò)Agri-Net第一行：農(nóng)場的個(gè)數(shù)，67【參考程序】#include<cstdio>#include<iostream>#include<algorithm>//sort()需要用到<algorithm>庫usingnamespacestd;structpoint{intx;inty;intv;};

//定義結(jié)構(gòu)類型，表示邊pointa[9901];

//存邊intfat[101];intn,i,j,x,m,tot,k;intfather(intx){if(fat[x]!=x)fat[x]=father(fat[x]);returnfat[x];}voidunionn(intx,inty){intfa=father(x);intfb=father(y);if(fa!=fb)fat[fa]=fb;}【參考程序】68intcmp(constpoint&a,constpoint&b)//sort()自定義的比較函數(shù){if(a.v<b.v)return1;elsereturn0;}intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>x;if(x!=0){m++;a[m].x=i;a[m].y=j;a[m].v=x;}}for(i=1;i<=n;i++)fat[i]=i;sort(a+1,a+m+1,cmp);//C++標(biāo)準(zhǔn)庫中自帶的快排

//cmp為自定義的比較函數(shù)。表示a數(shù)組的1-m按規(guī)則cmp排序intcmp(constpoint&a,constp69for(i=1;i<=m;i++){if(father(a[i].x)!=father(a[i].y)){unionn(a[i].x,a[i].y);tot+=a[i].v;k++;}if(k==n-1)break;}cout<<tot;return0;}最小生成樹和拓?fù)渑判蛘n件70上機(jī)練習(xí)1、局域網(wǎng)【問題描述】某個(gè)局域網(wǎng)內(nèi)有n(n<=100)臺(tái)計(jì)算機(jī)，由于搭建局域網(wǎng)時(shí)工作人員的疏忽，現(xiàn)在局域網(wǎng)內(nèi)的連接形成了回路，我們知道如果局域網(wǎng)形成回路那么數(shù)據(jù)將不停的在回路內(nèi)傳輸，造成網(wǎng)絡(luò)卡的現(xiàn)象。因?yàn)檫B接計(jì)算機(jī)的網(wǎng)線本身不同，所以有一些連線不是很暢通，我們用f(i,j)表示i,j之間連接的暢通程度(f(i,j)<=1000)，f(i,j)值越小表示i,j之間連接越通暢，f(i,j)為0表示i,j之間無網(wǎng)線連接?，F(xiàn)在我們需要解決回路問題，我們將除去一些連線，使得網(wǎng)絡(luò)中沒有回路，并且被除去網(wǎng)線的Σf(i,j)最大，請(qǐng)求出這個(gè)最大值?！据斎敫袷健康谝恍袃蓚€(gè)正整數(shù)nk接下來的k行每行三個(gè)正整數(shù)ijm表示i,j兩臺(tái)計(jì)算機(jī)之間有網(wǎng)線聯(lián)通，通暢程度為m?！据敵龈袷健恳粋€(gè)正整數(shù)，Σf(i,j)的最大值【輸入輸出樣例】【輸入樣例】【輸出樣例】551281311532453428上機(jī)練習(xí)1、局域網(wǎng)【輸入樣例】【輸出樣例】5515712、繁忙的都市【問題描述】城市C是一個(gè)非常繁忙的大都市，城市中的道路十分的擁擠，于是市長決定對(duì)其中的道路進(jìn)行改造。城市C的道路是這樣分布的：城市中有n個(gè)交叉路口，有些交叉路口之間有道路相連，兩個(gè)交叉路口之間最多有一條道路相連接。這些道路是雙向的，且把所有的交叉路口直接或間接的連接起來了。每條道路都有一個(gè)分值，分值越小表示這個(gè)道路越繁忙，越需要進(jìn)行改造。但是市政府的資金有限，市長希望進(jìn)行改造的道路越少越好，于是他提出下面的要求：改造的那些道路能夠把所有的交叉路口直接或間接的連通起來。在滿足要求1的情況下，改造的道路盡量少。在滿足要求1、2的情況下，改造的那些道路中分值最大值盡量小。【編程任務(wù)】作為市規(guī)劃局的你，應(yīng)當(dāng)作出最佳的決策，選擇那些道路應(yīng)當(dāng)被修建?！据斎敫袷健縞ity.in第一行有兩個(gè)整數(shù)n,m表示城市有n個(gè)交叉路口，m條道路。接下來m行是對(duì)每條道路的描述，u,v,c表示交叉路口u和v之間有道路相連，分值為c。(1≤n≤300，1≤c≤10000)【輸出格式】city.out兩個(gè)整數(shù)s,max，表示你選出了幾條道路，分值最大的那條道路的分值是多少?！据斎胼敵鰳永俊据斎霕永俊据敵鰳永?5123145247236348362、繁忙的都市【輸入樣例】【輸出樣例】452363723、聯(lián)絡(luò)員【問題描述】

Tyvj已經(jīng)一歲了，網(wǎng)站也由最初的幾個(gè)用戶增加到了上萬個(gè)用戶，隨著Tyvj網(wǎng)站的逐步壯大，管理員的數(shù)目也越來越多，現(xiàn)在你身為Tyvj管理層的聯(lián)絡(luò)員，希望你找到一些通信渠道，使得管理員兩兩都可以聯(lián)絡(luò)（直接或者是間接都可以）。Tyvj是一個(gè)公益性的網(wǎng)站，沒有過多的利潤，所以你要盡可能的使費(fèi)用少才可以。目前你已經(jīng)知道，Tyvj的通信渠道分為兩大類，一類是必選通信渠道，無論價(jià)格多少，你都需要把所有的都選擇上；還有一類是選擇性的通信渠道，你可以從中挑選一些作為最終管理員聯(lián)絡(luò)的通信渠道。數(shù)據(jù)保證給出的通行渠道可以讓所有的管理員聯(lián)通?！据斎敫袷健?/p>

第一行n，m表示Tyvj一共有n個(gè)管理員，有m個(gè)通信渠道第二行到m+1行，每行四個(gè)非負(fù)整數(shù)，p,u,v,w當(dāng)p=1時(shí)，表示這個(gè)通信渠道為必選通信渠道；當(dāng)p=2時(shí)，表示這個(gè)通信渠道為選擇性通信渠道；u,v,w表示本條信息描述的是u，v管理員之間的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示費(fèi)用?！据敵龈袷健?/p>

最小的通信費(fèi)用。3、聯(lián)絡(luò)員73561121123113411411225102255【輸入樣例】【輸出樣例】9樣例解釋：1-2-3-4-1存在四個(gè)必選渠道，形成一個(gè)環(huán)，互相可以到達(dá)。需要讓所有管理員聯(lián)通，需要聯(lián)通2和5號(hào)管理員，選擇費(fèi)用為5的渠道，所以總的費(fèi)用為9注意：u,v之間可能存在多條通信渠道，你的程序應(yīng)該累加所有u,v之間的必選通行渠道數(shù)據(jù)范圍：對(duì)于30%的數(shù)據(jù)，n<=10m<=100對(duì)于50%的數(shù)據(jù),n<=200m<=1000對(duì)于100%的數(shù)據(jù)，n<=2000m<=1000056【輸入樣例】【輸出樣例】樣例解釋：74拓?fù)渑判蛲負(fù)渑判?5AOV網(wǎng)

在日常生活中，一項(xiàng)大的工程可以看作是由若干個(gè)子工程（這些子工程稱為“活動(dòng)”）組成的集合，這些子工程（活動(dòng)）之間必定存在一些先后關(guān)系，即某些子工程（活動(dòng)）必須在其它一些子工程（活動(dòng)）完成之后才能開始，我們可以用有向圖來形象地表示這些子工程（活動(dòng)）之間的先后關(guān)系，子工程（活動(dòng)）為頂點(diǎn)，子工程（活動(dòng)）之間的先后關(guān)系為有向邊，這種有向圖稱為“頂點(diǎn)活動(dòng)網(wǎng)絡(luò)”，又稱“AOV網(wǎng)”。123567894AOV網(wǎng)12356789476在AOV網(wǎng)中，有向邊代表子工程（活動(dòng)）的先后關(guān)系，我們把一條有向邊起點(diǎn)的活動(dòng)成為終點(diǎn)活動(dòng)的前驅(qū)活動(dòng)，同理終點(diǎn)的活動(dòng)稱為起點(diǎn)活動(dòng)的后繼活動(dòng)。而只有當(dāng)一個(gè)活動(dòng)全部的前驅(qū)全部都完成之后，這個(gè)活動(dòng)才能進(jìn)行。例如在上圖中，只有當(dāng)工程1完成之后，工程2、3、4、5、6才能開始進(jìn)行。只有當(dāng)2、3、4全部完成之后，7才能開始進(jìn)行。一個(gè)AOV網(wǎng)必定是一個(gè)有向無環(huán)圖，即不應(yīng)該帶有回路。否則，會(huì)出現(xiàn)先后關(guān)系的自相矛盾。1234上圖就是一個(gè)出現(xiàn)環(huán)產(chǎn)生自相矛盾的情況。4是1的前驅(qū)，想完成1，必須先完成4。3是4的前驅(qū)，而2是3的前驅(qū)，1又是2的前驅(qū)。最后造成想完成1，必須先完成1本身，這顯然出現(xiàn)了矛盾。在AOV網(wǎng)中，有向邊代表子工程（活動(dòng)）的先后關(guān)系，我們把77拓?fù)渑判蛩惴?/p>

拓?fù)渑判蛩惴?，只適用于AOV網(wǎng)（有向無環(huán)圖）。把AOV網(wǎng)中的所有活動(dòng)排成一個(gè)序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，這個(gè)過程稱為“拓?fù)渑判颉?，所得到的活?dòng)序列稱為“拓?fù)湫蛄小?。一個(gè)AOV網(wǎng)的拓?fù)湫蛄惺遣晃ㄒ坏?，例如下面的這張圖，它的拓?fù)湫蛄锌梢允牵篈BCDE，也可以是ACBDE，或是ADBCE。在下圖所示的AOV網(wǎng)中，工程B和工程C顯然可以同時(shí)進(jìn)行，先后無所謂；但工程E卻要等工程B、C、D都完成以后才能進(jìn)行。ABCED

構(gòu)造拓?fù)湫蛄锌梢詭椭覀兒侠戆才乓粋€(gè)工程的進(jìn)度，由AOV網(wǎng)構(gòu)造拓?fù)湫蛄芯哂泻芨叩膶?shí)際應(yīng)用價(jià)值。拓?fù)渑判蛩惴ㄍ負(fù)渑判蛩惴?，只適用于AOV網(wǎng)（有向無78算法思想：構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄋ枷牒芎唵危?）選擇一個(gè)入度為0的頂點(diǎn)并輸出2）然后從AOV網(wǎng)中刪除此頂點(diǎn)及以此頂點(diǎn)為起點(diǎn)的所有關(guān)聯(lián)邊；3）重復(fù)上述兩步，直到不存在入度為0的頂點(diǎn)為止。4）若輸出的頂點(diǎn)數(shù)小于AOV網(wǎng)中的頂點(diǎn)數(shù)，則輸出“有回路信息”，否則輸出的頂點(diǎn)序列就是一種拓?fù)湫蛄袕牡谒牟娇梢钥闯?，拓?fù)渑判蚩梢杂脕砼袛嘁粋€(gè)有向圖是否有環(huán)。只有有向無環(huán)圖才存在拓?fù)湫蛄小Ｗ钚∩蓸浜屯負(fù)渑判蛘n件79算法實(shí)現(xiàn)：