信息學(xué)奧賽一本通 第4章第3-4節(jié) 圖論算法(C++版)

1、第四章 第三節(jié) 最短路徑算法 如下圖所示，我們把邊帶有權(quán)值的圖稱為帶權(quán)圖。邊的權(quán)值可以理 解為兩點(diǎn)之間的距離。一張圖中任意兩點(diǎn)間會(huì)有不同的路徑相連。最短 路徑就是指連接兩點(diǎn)的這些路徑中最短的一條。 我們有四種算法可以有效地解決最短路徑問(wèn)題。有一點(diǎn)需要讀者特 別注意：邊的權(quán)值可以為負(fù)。當(dāng)出現(xiàn)負(fù)邊權(quán)時(shí)，有些算法不適用。 一、求出最短路徑的長(zhǎng)度 以下沒(méi)有特別說(shuō)明的話，disuv表示從u到v最短路徑長(zhǎng)度，wuv表示連接u，v的邊的長(zhǎng)度。 1.Floyed-Warshall算法 O(N3) 簡(jiǎn)稱Floyed(弗洛伊德)算法，是最簡(jiǎn)單的最短路徑算法，可以計(jì)算圖中任意兩點(diǎn)間的最短路徑。Floyed 的時(shí)間復(fù)

2、雜度是O (N3)，適用于出現(xiàn)負(fù)邊權(quán)的情況。 算法描述： 初始化：點(diǎn)u、v如果有邊相連，則disuv=wuv。 如果不相連則disuv=0 x7fffffff For (k = 1; k = n; k+) For (i = 1; i = n; i+) For (j = 1; j disik + diskj) disij = disik + diskj; 算法結(jié)束：disij得出的就是從i到j(luò)的最短路徑。 算法分析 k = n; k+) For (i = 1; i = n; i+) For (j = 1; j = n; j+) disij = disij | (disik 用這個(gè)辦法可以判斷一張

3、圖中的兩點(diǎn)是否相連。 最后再?gòu)?qiáng)調(diào)一點(diǎn)：用來(lái)循環(huán)中間點(diǎn)的變量k必須放在 最外面一層循環(huán)。 【例4-1】、最短路徑問(wèn)題 【問(wèn)題描述】 平面上有n個(gè)點(diǎn)（n=100），每個(gè)點(diǎn)的坐標(biāo)均在-1000010000之間。其中的一些點(diǎn)之間有連 線。 若有連線，則表示可從一個(gè)點(diǎn)到達(dá)另一個(gè)點(diǎn)，即兩點(diǎn)間有通路，通路的距離為兩點(diǎn)間的直線距 離。現(xiàn)在的 任務(wù)是找出從一點(diǎn)到另一點(diǎn)之間的最短路徑。 【輸入格式】 輸入文件為short.in，共n+m+3行，其中: 第一行為整數(shù)n。 第2行到第n+1行（共n行） ，每行兩個(gè)整數(shù)x和y，描述了一個(gè)點(diǎn)的坐標(biāo)。 第n+2行為一個(gè)整數(shù)m，表示圖中連線的個(gè)數(shù)。 此后的m 行，每行描述一條

4、連線，由兩個(gè)整數(shù)i和j組成，表示第i個(gè)點(diǎn)和第j個(gè)點(diǎn)之間有連線。 最后一行：兩個(gè)整數(shù)s和t，分別表示源點(diǎn)和目標(biāo)點(diǎn)。 【輸出格式】 輸出文件為short.out，僅一行，一個(gè)實(shí)數(shù)（保留兩位小數(shù)），表示從s到t的最短路徑長(zhǎng)度。 【輸入樣例輸入樣例】 5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 【輸出樣例輸出樣例】 3.41 【參考程序】 #include #include #include #include using namespace std; int a1013; double f101101; int n,i,j,k,x,y,m,s,e;

5、int main() freopen(short.in,r,stdin); freopen(short.out,w,stdout); cin n; for (i = 1; i ai1 ai2; cin m; memset(f,0 x7f,sizeof(f); /初始化f數(shù)組為最大值 for (i = 1; i x y; fyx = fxy = sqrt(pow(double(ax1-ay1),2)+pow(double(ax2- ay2),2); /pow(x,y)表示xy，其中x,y必須為double類型，要用cmath庫(kù) cin s e; for (k = 1; k = n; k+) /f

6、loyed 最短路算法 for (i = 1; i = n; i+) for (j = 1; j = n; j+) if (i != j) printf(%.2lfn,fse); return 0; 【例例4-2】牛的旅行牛的旅行 【問(wèn)題描述問(wèn)題描述】 農(nóng)民農(nóng)民JohnJohn的農(nóng)場(chǎng)里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一的農(nóng)場(chǎng)里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一 片所有連通的牧區(qū)稱為一個(gè)牧場(chǎng)。但是就目前而言，你能看到至少有兩片所有連通的牧區(qū)稱為一個(gè)牧場(chǎng)。但是就目前而言，你能看到至少有兩 個(gè)牧區(qū)不連通。現(xiàn)在，個(gè)牧區(qū)不連通。現(xiàn)在，JohnJohn想在農(nóng)場(chǎng)里添加一條路徑想在農(nóng)場(chǎng)里添加一

7、條路徑 ( ( 注意，恰好一注意，恰好一 條條 ) )。對(duì)這條路徑有這樣的限制：一個(gè)牧場(chǎng)的直徑就是牧場(chǎng)中最遠(yuǎn)的兩。對(duì)這條路徑有這樣的限制：一個(gè)牧場(chǎng)的直徑就是牧場(chǎng)中最遠(yuǎn)的兩 個(gè)牧區(qū)的距離個(gè)牧區(qū)的距離 ( ( 本題中所提到的所有距離指的都是最短的距離本題中所提到的所有距離指的都是最短的距離 ) )?？肌？?慮如下的兩個(gè)牧場(chǎng)，圖是有慮如下的兩個(gè)牧場(chǎng)，圖是有5 5個(gè)牧區(qū)的牧場(chǎng)，牧區(qū)用個(gè)牧區(qū)的牧場(chǎng)，牧區(qū)用“* *”表示，路徑表示，路徑 用直線表示。每一個(gè)牧區(qū)都有自己的坐標(biāo)：用直線表示。每一個(gè)牧區(qū)都有自己的坐標(biāo)： 圖所示的牧場(chǎng)的直徑大約是圖所示的牧場(chǎng)的直徑大約是12.07106, 12.07106, 最遠(yuǎn)

8、的兩個(gè)牧區(qū)是最遠(yuǎn)的兩個(gè)牧區(qū)是A A 和和E E，它們之間的最短路徑是，它們之間的最短路徑是A-B-EA-B-E。 這兩個(gè)牧場(chǎng)都在這兩個(gè)牧場(chǎng)都在JohnJohn的的 農(nóng)場(chǎng)上。農(nóng)場(chǎng)上。JohnJohn將會(huì)在兩個(gè)牧場(chǎng)中各選一個(gè)牧區(qū)，然后用一條路徑連將會(huì)在兩個(gè)牧場(chǎng)中各選一個(gè)牧區(qū)，然后用一條路徑連 起來(lái)，使得連通后這個(gè)新的更大的牧場(chǎng)有最小的直徑。注意，如果起來(lái)，使得連通后這個(gè)新的更大的牧場(chǎng)有最小的直徑。注意，如果 兩條路徑中途相交，我們不認(rèn)為它們是連通的。只有兩條路徑在同兩條路徑中途相交，我們不認(rèn)為它們是連通的。只有兩條路徑在同 一個(gè)牧區(qū)相交，我們才認(rèn)為它們是連通的。一個(gè)牧區(qū)相交，我們才認(rèn)為它們是連通的

9、。 現(xiàn)在請(qǐng)你編程找現(xiàn)在請(qǐng)你編程找 出一條連接兩個(gè)不同牧場(chǎng)的路徑，使得連上這條路徑后，這個(gè)更大出一條連接兩個(gè)不同牧場(chǎng)的路徑，使得連上這條路徑后，這個(gè)更大 的新牧場(chǎng)有最小的直徑。的新牧場(chǎng)有最小的直徑。 【輸入格式輸入格式】 第第 1 1 行：一個(gè)整數(shù)行：一個(gè)整數(shù)N (1 = N = N (1 = N = 150), 150), 表示牧區(qū)數(shù)；表示牧區(qū)數(shù)； 第第 2 2 到到 N+1 N+1 行：每行兩個(gè)整數(shù)行：每行兩個(gè)整數(shù)X X，Y ( 0 = XY ( 0 = X，Y= Y= 100000 )100000 )， 表示表示N N個(gè)牧區(qū)的坐標(biāo)。每個(gè)牧個(gè)牧區(qū)的坐標(biāo)。每個(gè)牧 區(qū)的坐標(biāo)都是不一樣的。區(qū)的坐標(biāo)

10、都是不一樣的。 第第 N+2 N+2 行行 到第到第 2 2* *N+1 N+1 行：每行包括行：每行包括N N個(gè)數(shù)字個(gè)數(shù)字 ( 0( 0或或 1 ) 1 ) 表示一個(gè)對(duì)稱鄰接矩陣。表示一個(gè)對(duì)稱鄰接矩陣。 例如，例如， 題目描述中的兩個(gè)牧場(chǎng)的矩陣描述如下：題目描述中的兩個(gè)牧場(chǎng)的矩陣描述如下： A B C D E F G H A B C D E F G H A 0 1 0 0 0 0 0 0 A 0 1 0 0 0 0 0 0 B 1 0 1 1 1 0 0 0 B 1 0 1 1 1 0 0 0 C 0 1 0 0 1 0 0 0 C 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0

11、 0 0 D 0 1 0 0 1 0 0 0 E 0 1 1 1 0 0 0 0 E 0 1 1 1 0 0 0 0 F 0 0 0 0 0 0 1 0 F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0 H 0 0 0 0 0 0 1 0 輸入數(shù)據(jù)中至少包括兩個(gè)不連通的牧區(qū)。輸入數(shù)據(jù)中至少包括兩個(gè)不連通的牧區(qū)。 【輸出格式輸出格式】 只有一行，包括一個(gè)實(shí)數(shù)，表示所只有一行，包括一個(gè)實(shí)數(shù)，表示所 求答案。數(shù)字保留六位小數(shù)。求答案。數(shù)字保留六位小數(shù)。 【輸入樣例輸入樣例】 8 8 10 1010 10 1

12、5 1015 10 20 1020 10 15 1515 15 20 1520 15 30 1530 15 25 1025 10 30 1030 10 0100000001000000 1011100010111000 0100100001001000 0100100001001000 0111000001110000 0000001000000010 0000010100000101 0000001000000010 【輸出樣例輸出樣例】 22.07106822.071068 【算法分析】 用Floyed求出任兩點(diǎn)間的最短路，然后求出 每個(gè)點(diǎn)到所有可達(dá)的點(diǎn)的最大距離，記做mdisi 。（Fl

13、oyed算法） r1=max(mdisi) 然后枚舉不連通的兩點(diǎn)i,j，把他們連通，則新 的直徑是mdisi+mdisj+(i,j)間的距離。 r2=min(mdisi+mdisj+disi,j) re=max(r1,r2) re就是所求。 【參考程序參考程序】 #include#include #include#include using namespace std;using namespace std; double f151151,m151,minx,r,temp,x151,y151,maxint=1e12;double f151151,m151,minx,r,temp,x151,y1

14、51,maxint=1e12; double dist(int i,int j)double dist(int i,int j) return sqrt(xi-xj) return sqrt(xi-xj)* *(xi-xj)+(yi-yj)(xi-xj)+(yi-yj)* *(yi-yj) ; (yi-yj) ; int main()int main() int i,j,n,k;char c; int i,j,n,k;char c; cinn; cinn; for(i=1;ixiyi; for(i=1;ixiyi; for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1

15、;j=n;j+) for(j=1;jc; cinc; if(c=1)fij=dist(i,j); if(c=1)fij=dist(i,j); else fij=maxint; else fij=maxint; for(k=1;k=n;k+) for(k=1;k=n;k+) for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;j=n;j+) if(i!=j fij=fik+fkj; memset(m,0,sizeof(m);memset(m,0,sizeof(m); for(i=1;i=n;i+) for(i=1;i=n;i+) for

16、(j=1;j=n;j+) for(j=1;j=n;j+) if(fijmaxint-1 if(fijmaxint-1 minx=1e20; minx=1e20; for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;jmaxint-1) if(i!=j temp=dist(i,j); if(minxmi+mj+temp)minx=mi+mj+temp; if(minxmi+mj+temp)minx=mi+mj+temp; r=0; r=0; for(i=1;iminx)minx=mi; for(i=1;iminx)minx=mi; pr

17、intf(%.6lf,minx); printf(%.6lf,minx); return 0; return 0; 2.2.Dijkstra算法算法O (N2) 用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，是一種單源最短路徑算法。也就用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，是一種單源最短路徑算法。也就 是說(shuō)，只能計(jì)算起點(diǎn)只有一個(gè)的情況。是說(shuō)，只能計(jì)算起點(diǎn)只有一個(gè)的情況。 Dijkstraijkstra的時(shí)間復(fù)雜度是的時(shí)間復(fù)雜度是O (N2)，它不能處理存在負(fù)邊權(quán)的情況。，它不能處理存在負(fù)邊權(quán)的情況。 算法描述：算法描述： 設(shè)起點(diǎn)為設(shè)起點(diǎn)為s，disv表示從表示從s到到v的最短路徑，的最

18、短路徑，prev為為v的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。 a)a)初始化：初始化：disv=(vs); diss=0; pres=0 0; b)b)For (i = 1; i = n ; i+)(i = 1; i = n ; i+) 1.在沒(méi)有被訪問(wèn)過(guò)的點(diǎn)中找一個(gè)頂點(diǎn)在沒(méi)有被訪問(wèn)過(guò)的點(diǎn)中找一個(gè)頂點(diǎn)u使得使得disu是最小的。是最小的。 2.u標(biāo)記為已確定最短路徑標(biāo)記為已確定最短路徑 3.For 與與u相連的每個(gè)未確定最短路徑的頂點(diǎn)相連的每個(gè)未確定最短路徑的頂點(diǎn)v if ( (disu+wuv disv) ) disv = disu + wuv; prev = u; c)c)算

19、法結(jié)束：算法結(jié)束：disv為為s到到v的最短距離；的最短距離；prev為為v的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。 算法分析算法分析 int a1013; double c101; bool b101; double f101101; int n,i,j,k,x,y,m,s,e; double minl; double maxx = 1e30; int main() cin n; for (i = 1; i ai1 ai2; for (i = 1; i = n; i+) for(j = 1; j m; for (i = 1; i x y; fxy = fyx = = sqrt(p

20、ow(double(ax1-ay1),2)+pow(double(ax2-ay2),2); ; cin s e; for (i = 1; i = n; i+) ci = fsi; memset(b,false,sizeof(b); /dijkstra /dijkstra 最短路最短路 bs = true; cs = 0; for (i = 1; i = n-1; i+) minl = maxx; k = 0; for (j = 1; j = n; j+) / /查找可以更新的點(diǎn)查找可以更新的點(diǎn) if (! bj) k = j; if (k = 0) break; bk = true; for

21、(j = 1; j = n; j+) if (ck + fkj cj) cj = ck + fkj; printf(%.2lfn,ce); return 0; 【例例4-4】最小花費(fèi)最小花費(fèi) 【問(wèn)題描述問(wèn)題描述】 在在n n個(gè)人中，某些人的銀行賬號(hào)之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費(fèi)各不相同。個(gè)人中，某些人的銀行賬號(hào)之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費(fèi)各不相同。 給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)，請(qǐng)問(wèn)給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)，請(qǐng)問(wèn)A A最少需要多少錢(qián)使得最少需要多少錢(qián)使得 轉(zhuǎn)賬后轉(zhuǎn)賬后B B收到收到100100元。元。 【輸入格式

22、輸入格式】 第一行輸入兩個(gè)正整數(shù)第一行輸入兩個(gè)正整數(shù)n,mn,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對(duì)數(shù)。，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對(duì)數(shù)。 以下以下m m行每行輸入三個(gè)正整數(shù)行每行輸入三個(gè)正整數(shù)x,y,zx,y,z，表示標(biāo)號(hào)為，表示標(biāo)號(hào)為x x的人和標(biāo)號(hào)為的人和標(biāo)號(hào)為y y的人之間互相轉(zhuǎn)賬需要扣的人之間互相轉(zhuǎn)賬需要扣 除除z%z%的手續(xù)費(fèi)的手續(xù)費(fèi) (z100)(z100)。 最后一行輸入兩個(gè)正整數(shù)最后一行輸入兩個(gè)正整數(shù)A,BA,B。數(shù)據(jù)保證。數(shù)據(jù)保證A A與與B B之間可以直接或間接地轉(zhuǎn)賬。之間可以直接或間接地轉(zhuǎn)賬。 【輸出格式輸出格式】 輸出輸出A A使得使得B B到賬到賬1001

23、00元最少需要的總費(fèi)用。精確到小數(shù)點(diǎn)后元最少需要的總費(fèi)用。精確到小數(shù)點(diǎn)后8 8位。位。 【輸入樣例輸入樣例】 3 3 3 3 1 2 1 1 2 1 2 3 2 2 3 2 1 3 3 1 3 3 1 3 1 3 【輸出樣例輸出樣例】 103.07153164 103.07153164 【數(shù)據(jù)規(guī)模數(shù)據(jù)規(guī)?！?1=n=2000 1=n=2000 【參考程序參考程序】 #include#include using namespace std;using namespace std; double a20012001,dis2001=0,minn;double a20012001,dis2001=0

24、,minn; int n,m,i,j,k,x,y,f2001=0;int n,m,i,j,k,x,y,f2001=0; void init()void init() cinnm; cinnm; for(i=1;i=m;i+) for(i=1;ixy; cinxy; void dijkstra(int x)void dijkstra(int x) for(i=1;i=n;i+)disi=axi; for(i=1;i=n;i+)disi=axi; disx=1;fx=1; disx=1;fx=1; for(i=1;i=n-1;i+) for(i=1;i=n-1;i+) minn=0; minn=0

25、; for(j=1;j=n;j+) for(j=1;jminn)k=j;minn=disj; if(fj=0minn=disj; fk=1; fk=1; if(k=y)break; if(k=y)break; for(j=1;j=n;j+) for(j=1;jdisj)disj=diskakjdisj)disj=disk* *akj;akj; int main()int main() init(); init(); dijkstra(x); dijkstra(x); printf(%0.8lf,100/disy); printf(%0.8lf,100/disy); return 0; retu

26、rn 0; 3.3.Bellman-Ford算法算法O(NE) 簡(jiǎn)稱簡(jiǎn)稱FordFord（福特）算法，同樣是用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算（福特）算法，同樣是用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算 法，也是一種單源最短路徑算法。法，也是一種單源最短路徑算法。 能夠處理存在負(fù)邊權(quán)的情況，但無(wú)法處理存在負(fù)權(quán)回路的情況（下文會(huì)有詳細(xì)說(shuō)能夠處理存在負(fù)邊權(quán)的情況，但無(wú)法處理存在負(fù)權(quán)回路的情況（下文會(huì)有詳細(xì)說(shuō) 明）。明）。 算法時(shí)間復(fù)雜度：算法時(shí)間復(fù)雜度：O(NE)，N是頂點(diǎn)數(shù)，是頂點(diǎn)數(shù)，E是邊數(shù)。是邊數(shù)。 算法實(shí)現(xiàn)：算法實(shí)現(xiàn)： 設(shè)設(shè)s為起點(diǎn)，為起點(diǎn)，disv即為即為s到到v的最短距離，的

27、最短距離，prev為為v前驅(qū)。前驅(qū)。wj是邊是邊j的長(zhǎng)度，且的長(zhǎng)度，且j連連 接接u、v。 初始化：初始化：diss=0,disv=（vs），），pres=0 For (i = 1; i = n-1; i+)(i = 1; i = n-1; i+) For (j = 1; j = E; j+)(j = 1; j = E; j+) / /注意要枚舉所有邊，不能枚舉點(diǎn)。注意要枚舉所有邊，不能枚舉點(diǎn)。 if ( (disu+wjdisv) ) /u /u、v分別是這條邊連接的兩個(gè)點(diǎn)。分別是這條邊連接的兩個(gè)點(diǎn)。 disv =disu + wj; prev = u; 算法分析算法分析 int main(

28、) double a1013,dis1001,w1001,min1; int n,m,x,y,k,f10013,s,t; bool b101; cinn; for (int i=1;im; for (int i=1;i=m;i+) /初始化數(shù)組初始化數(shù)組dis，f disi=0 x7fffffffffffff/3/3; fi1 = fi2 = fi1 = fi2 = 0 x7fffffffffffff/3/3; for (int i=1;ist; diss=0; for (int i=1;i=n;i+) / /算法主體算法主體 for (int j=1;j=m;j+) if (disfj1+w

29、jdisfj2) disfj2=disfj1+wj; if (disfj2+wjdisu+wudisvdisu+wuvv) ) disv=disu+wu disv=disu+wuv;v; prev=u; prev=u; i if f (!(!existvexistv) ) / /隊(duì)列中不存在隊(duì)列中不存在v v點(diǎn)，點(diǎn)，v v入隊(duì)。入隊(duì)。 / /尾指針下移一位，尾指針下移一位，v v入隊(duì)入隊(duì); ; e existv=true;xistv=true; while (head tail); while (head tail); 循環(huán)隊(duì)列： 采用循環(huán)隊(duì)列能夠降低隊(duì)列大小，隊(duì)列長(zhǎng)度只需開(kāi)到2*n+5即可。

30、例題中的參考程序使用了循環(huán)隊(duì)列。 【例例4-6】、香甜的黃油、香甜的黃油(Sweet Butter) ) 【問(wèn)題描述問(wèn)題描述】 農(nóng)夫農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道N（1=N=500）只奶牛會(huì)過(guò)來(lái)舔它，這樣就能做出能賣好價(jià)錢(qián)的超）只奶牛會(huì)過(guò)來(lái)舔它，這樣就能做出能賣好價(jià)錢(qián)的超 甜黃油。當(dāng)然，他將付出額外的費(fèi)用在奶牛上。甜黃油。當(dāng)然，他將付出額外的費(fèi)用在奶牛上。 農(nóng)夫農(nóng)夫John很狡猾。像以前的巴甫洛夫，他知道他可以訓(xùn)練這些奶牛，讓它們?cè)诼?tīng)到鈴聲時(shí)去一個(gè)特定的牧場(chǎng)。他打算將糖放在那里

31、然后下午發(fā)出鈴聲，以至很狡猾。像以前的巴甫洛夫，他知道他可以訓(xùn)練這些奶牛，讓它們?cè)诼?tīng)到鈴聲時(shí)去一個(gè)特定的牧場(chǎng)。他打算將糖放在那里然后下午發(fā)出鈴聲，以至 他可以在晚上擠奶。他可以在晚上擠奶。 農(nóng)夫農(nóng)夫John知道每只奶牛都在各自喜歡的牧場(chǎng)（一個(gè)牧場(chǎng)不一定只有一頭牛）。給出各頭牛在的牧場(chǎng)和牧場(chǎng)間的路線，找出使所有牛到達(dá)的路程和最短的牧場(chǎng)知道每只奶牛都在各自喜歡的牧場(chǎng)（一個(gè)牧場(chǎng)不一定只有一頭牛）。給出各頭牛在的牧場(chǎng)和牧場(chǎng)間的路線，找出使所有牛到達(dá)的路程和最短的牧場(chǎng) （他將把糖放在那）。（他將把糖放在那）。 【輸入格式輸入格式】butter.in 第一行第一行: 三個(gè)數(shù)：奶牛數(shù)三個(gè)數(shù)：奶牛數(shù)N，牧場(chǎng)數(shù)

32、，牧場(chǎng)數(shù)P（2=P=800），牧場(chǎng)間道路數(shù)），牧場(chǎng)間道路數(shù)C(1=C=1450)。 第二行到第第二行到第N+1行行: 1到到N頭奶牛所在的牧場(chǎng)號(hào)。頭奶牛所在的牧場(chǎng)號(hào)。 第第N+2行到第行到第N+C+1行：每行有三個(gè)數(shù)：相連的牧場(chǎng)行：每行有三個(gè)數(shù)：相連的牧場(chǎng)A、B，兩牧場(chǎng)間距（，兩牧場(chǎng)間距（1=D=255），當(dāng)然，連接是雙向的。），當(dāng)然，連接是雙向的。 【輸出格式輸出格式】butter.out 一行一行 輸出奶牛必須行走的最小的距離和輸出奶牛必須行走的最小的距離和. 【輸入樣例輸入樣例】 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 樣例圖形樣例圖形 P2

33、P2 P1 -1- C1P1 -1- C1 | | | | 5 7 3 5 7 3 | | | C3 | C3 C2 -5- C2 -5- P3 P4 P3 P4 【輸出樣例輸出樣例】 8 / /說(shuō)明：放在說(shuō)明：放在4號(hào)牧場(chǎng)最優(yōu)號(hào)牧場(chǎng)最優(yōu) 【參考程序參考程序】 #include#include #include#include #include#include using namespace std;using namespace std; int n,p,c,i,j,x,y,t,min1,head,tail,tot,u;int n,p,c,i,j,x,y,t,min1,head,tail,t

34、ot,u; int a801801,b501,dis801,num801,w801801,team1601;int a801801,b501,dis801,num801,w801801,team1601; bool exist801;bool exist801; int main()int main() freopen(butter.in,r,stdin); freopen(butter.in,r,stdin); freopen(butter.out,w,stdout); freopen(butter.out,w,stdout); cinnpc; cinnpc; for(i=1;i=p;i+)

35、 for(i=1;i=p;i+) bi=0;bi=0; numi=0;numi=0; for(j=1;j=p;j+) for(j=1;j=p;j+) wij= wij=0 x7fffffff/30 x7fffffff/3; ; for(i=1;i=n;i+) for(i=1;ibi; cinbi; for(i=1;i=c;i+) for(i=1;ixyt; cinxyt; wxy=t; wxy=t; ax+numx=y; ax+numx=y; ay+numy=x; ay+numy=x; wyx=wxy; wyx=wxy; min1= min1=0 x7fffffff0 x7fffffff/3/

36、3; ; for(i=1;i=p;i+) for(i=1;i=p;i+) for(j=1;j=p;j+) disj= for(j=1;j=p;j+) disj=0 x7fffffff0 x7fffffff/3/3; ; memset(team,0,sizeof(team); memset(team,0,sizeof(team); / /隊(duì)列數(shù)組初始化隊(duì)列數(shù)組初始化 memset(exist,false,sizeof(exist); memset(exist,false,sizeof(exist); /exist /exist標(biāo)志初始化標(biāo)志初始化 disi=0;team1=i;head=0;ta

37、il=1;existi=true; disi=0;team1=i;head=0;tail=1;existi=true; / /起始點(diǎn)入隊(duì)起始點(diǎn)入隊(duì) do do head+; head+; head=(head-1)%1601)+1; head=(head-1)%1601)+1; / /循環(huán)隊(duì)列處理循環(huán)隊(duì)列處理 u=teamhead; u=teamhead; existu=false; existu=false; for(j=1;j= for(j=1;jdisu+wuauj) if (disaujdisu+wuauj) disauj=disu+wuauj; disauj=disu+wuauj;

38、if (!existauj) if (!existauj) tail+; tail+; tail=(tail-1)%1601)+1; tail=(tail-1)%1601)+1; teamtail=auj; teamtail=auj; existauj=true; existauj=true; while(head!=tail); while(head!=tail); tot=0; tot=0; for(j=1;j=n;j+) for(j=1;j=n;j+) t totot+ +=disbj;=disbj; if (totmin1) min1=tot; if (totmin1) min1=to

39、t; coutmin1; coutmin1; return 0; return 0; 二、輸出最短路徑二、輸出最短路徑 1.1.單源最短路徑的輸出單源最短路徑的輸出 Dijkstraijkstra，Bellman-Ford，SPFA都是單源最短路徑算法，它們的共同點(diǎn)是都都是單源最短路徑算法，它們的共同點(diǎn)是都 有一個(gè)數(shù)組有一個(gè)數(shù)組prex 用來(lái)記錄從起點(diǎn)到用來(lái)記錄從起點(diǎn)到x的最短路徑中，的最短路徑中，x的前驅(qū)結(jié)點(diǎn)是哪個(gè)。的前驅(qū)結(jié)點(diǎn)是哪個(gè)。 每次更新，我們就給每次更新，我們就給prex 賦一個(gè)新值，結(jié)合上面的思想講解，相信對(duì)于記錄賦一個(gè)新值，結(jié)合上面的思想講解，相信對(duì)于記錄 某點(diǎn)的前驅(qū)結(jié)點(diǎn)是不難理

40、解的。那么怎么利用某點(diǎn)的前驅(qū)結(jié)點(diǎn)是不難理解的。那么怎么利用prex 數(shù)組輸出最短路徑方案呢？數(shù)組輸出最短路徑方案呢？ 【例【例4-7】、最短路徑問(wèn)題】、最短路徑問(wèn)題(輸出路徑輸出路徑) 要求改寫(xiě)程序，用要求改寫(xiě)程序，用Dijkstra、Bellman-Ford、SPFA算法輸出最短路徑的方案。算法輸出最短路徑的方案。 使用一個(gè)小小的遞歸過(guò)程就能解決這一問(wèn)題。使用一個(gè)小小的遞歸過(guò)程就能解決這一問(wèn)題。 void print(int x) if (pre if (preax = 0) return; /x = 0) return; /起點(diǎn)的前驅(qū)我們已設(shè)為起點(diǎn)的前驅(qū)我們已設(shè)為0 print(preax

41、); cout x; / /主程序中：主程序中： mainmain （進(jìn)行（進(jìn)行Dijkstra或或Bellman-Ford，SPFA運(yùn)算）運(yùn)算） cout sout s; print print(e); /s /s是起點(diǎn)，是起點(diǎn)，e是終點(diǎn)是終點(diǎn) 2.2.Floyed算法輸出最短路徑算法輸出最短路徑 FloyedFloyed算法輸出路徑也是采用記錄前驅(qū)點(diǎn)的方式。因?yàn)樗惴ㄝ敵雎窂揭彩遣捎糜涗浨膀?qū)點(diǎn)的方式。因?yàn)閒loyed是計(jì)算任意兩點(diǎn)是計(jì)算任意兩點(diǎn) 間最短路徑的算法，間最短路徑的算法，disij記錄從記錄從i到到j(luò)的最短路徑值。故而我們定義的最短路徑值。故而我們定義preij 為一個(gè)二維數(shù)組，記

42、錄從為一個(gè)二維數(shù)組，記錄從i到到j(luò)的最短路徑中，的最短路徑中，j的前驅(qū)點(diǎn)是哪一個(gè)。的前驅(qū)點(diǎn)是哪一個(gè)。 【例例4-8】、最短路徑問(wèn)題、最短路徑問(wèn)題(Floyed法輸出路徑法輸出路徑) 要求改寫(xiě)要求改寫(xiě)Floyed的程序，模仿的程序，模仿Dijkstra輸出路徑的方法用輸出路徑的方法用floyed輸出最短路徑方案。輸出最短路徑方案。 【參考程序參考程序】 #include #include #include using namespace std; double dis101101; int x101,y101; int pre101101; int n,i,j,k,m,a,b; int pf(i

43、nt x) return x*x; void print(int x) if (preax = 0) return; /prea if (preax = 0) return; /preaa=0,a=0,說(shuō)明已經(jīng)遞歸到起點(diǎn)說(shuō)明已經(jīng)遞歸到起點(diǎn)a print(preax); cout n; cin n; for (i = 1; i = n; i+) for (i = 1; i xi yi; cin xi yi; memset(dis,0 x7f,sizeof(dis); memset(dis,0 x7f,sizeof(dis); /初始化數(shù)組初始化數(shù)組 cin m; cin m; memset(pr

44、e,0,sizeof(pre); memset(pre,0,sizeof(pre); / /初始化前驅(qū)數(shù)組初始化前驅(qū)數(shù)組 for (i = 1; i = m; i+) for (i = 1; i a b; cin a b; disab = disba = sqrt(pf(xa-xb)+pf(ya-yb); disab = disba = sqrt(pf(xa-xb)+pf(ya-yb); preab = a; preab = a; /a /a與與b b相連，自然從相連，自然從a a到到b b的最短路徑的最短路徑b b的前驅(qū)是的前驅(qū)是a a preba = b; preba = b; cin a

45、 b; cin a b; for (k = 1; k = n; k+) for (k = 1; k = n; k+) /floyed /floyed 最短路最短路 for (i = 1; i = n; i+) for (i = 1; i = n; i+) for (j = 1; j = n; j+) for (j = 1; j disik+diskj) if (disij disik+diskj) disij = disik + diskj; disij = disik + diskj; preij = prekj; preij = prekj; / /從從i i到到j(luò) j的最短路徑更新為的最

46、短路徑更新為i ik kj j，那么，那么i i到到j(luò) j最短路徑最短路徑j(luò) j的前驅(qū)就肯定與的前驅(qū)就肯定與k k到到j(luò) j最短路徑最短路徑j(luò) j的前驅(qū)相同。的前驅(qū)相同。 cout a; cout a; print(b); /a print(b); /a是起點(diǎn)，是起點(diǎn)，b b是終點(diǎn)是終點(diǎn) return 0; return 0; 最后再稍微提一提有向圖求最短路徑的方法：對(duì)有向圖求最短路徑上面的算法可以直接使用，只需注意如最后再稍微提一提有向圖求最短路徑的方法：對(duì)有向圖求最短路徑上面的算法可以直接使用，只需注意如 果從果從i到到j(luò)只有一條有向邊，只有一條有向邊，wij賦值為這條邊的權(quán)值，而將賦值為

47、這條邊的權(quán)值，而將wji賦值為無(wú)窮大即可。賦值為無(wú)窮大即可。 【上機(jī)練習(xí)】 1、信使 【問(wèn)題描述】 戰(zhàn)爭(zhēng)時(shí)期，前線有n個(gè)哨所，每個(gè)哨所可能會(huì)與其他若干個(gè)哨所之間有通信聯(lián)系。信 使負(fù)責(zé)在哨所之間傳遞信息，當(dāng)然，這是要花費(fèi)一定時(shí)間的（以天為單位）。指揮部 設(shè)在第一個(gè)哨所。當(dāng)指揮部下達(dá)一個(gè)命令后，指揮部就派出若干個(gè)信使向與指揮部相 連的哨所送信。當(dāng)一個(gè)哨所接到信后，這個(gè)哨所內(nèi)的信使們也以同樣的方式向其他哨 所送信。直至所有n個(gè)哨所全部接到命令后，送信才算成功。因?yàn)闇?zhǔn)備充足，每個(gè)哨所 內(nèi)都安排了足夠的信使（如果一個(gè)哨所與其他k個(gè)哨所有通信聯(lián)系的話，這個(gè)哨所內(nèi)至 少會(huì)配備k個(gè)信使）。 現(xiàn)在總指揮請(qǐng)你編一

48、個(gè)程序，計(jì)算出完成整個(gè)送信過(guò)程最短需要多少時(shí)間。 【輸入格式】 輸入文件msner.in，第1行有兩個(gè)整數(shù)n和m，中間用1個(gè)空格隔開(kāi)，分別表示有n個(gè) 哨所和m條通信線路。1=n=100。 第2至m+1行：每行三個(gè)整數(shù)i、j、k，中間用1個(gè)空格隔開(kāi)，表示第i個(gè)和第j個(gè)哨所之 間存在通信線路，且這條線路要花費(fèi)k天。 【輸出格式】 輸出文件msner.out，僅一個(gè)整數(shù)，表示完成整個(gè)送信過(guò)程的最短時(shí)間。如果不是所 有的哨所都能收到信，就輸出-1。 【輸入樣例】 4 4 1 2 4 2 3 7 2 4 1 3 4 6 【輸出樣例】 11 2 2、最優(yōu)乘車、最優(yōu)乘車 【問(wèn)題描述問(wèn)題描述】 H H城是一個(gè)

49、旅游勝地，每年都有成千上萬(wàn)的人前來(lái)觀光。為方便游客，巴士公司在各個(gè)旅游景點(diǎn)及賓館，城是一個(gè)旅游勝地，每年都有成千上萬(wàn)的人前來(lái)觀光。為方便游客，巴士公司在各個(gè)旅游景點(diǎn)及賓館， 飯店等地都設(shè)置了巴士站并開(kāi)通了一些單程巴上線路。每條單程巴士線路從某個(gè)巴士站出發(fā)，依次途經(jīng)若干個(gè)飯店等地都設(shè)置了巴士站并開(kāi)通了一些單程巴上線路。每條單程巴士線路從某個(gè)巴士站出發(fā)，依次途經(jīng)若干個(gè) 巴士站，最終到達(dá)終點(diǎn)巴士站。巴士站，最終到達(dá)終點(diǎn)巴士站。 一名旅客最近到一名旅客最近到H城旅游，他很想去城旅游，他很想去S公園游玩，但如果從他所在的飯店沒(méi)有一路巴士可以直接到達(dá)公園游玩，但如果從他所在的飯店沒(méi)有一路巴士可以直接到達(dá)S

50、公園，公園， 則他可能要先乘某一路巴士坐幾站，再下來(lái)?yè)Q乘同一站臺(tái)的另一路巴士則他可能要先乘某一路巴士坐幾站，再下來(lái)?yè)Q乘同一站臺(tái)的另一路巴士, 這樣換乘幾次后到達(dá)這樣換乘幾次后到達(dá)S公園。公園。 現(xiàn)在用整數(shù)現(xiàn)在用整數(shù)1,2 2,N N 給給H城的所有的巴士站編號(hào)，約定這名旅客所在飯店的巴士站編號(hào)為城的所有的巴士站編號(hào)，約定這名旅客所在飯店的巴士站編號(hào)為1，S公園巴士站公園巴士站 的編號(hào)為的編號(hào)為N。 寫(xiě)一個(gè)程序，幫助這名旅客尋找一個(gè)最優(yōu)乘車方案寫(xiě)一個(gè)程序，幫助這名旅客尋找一個(gè)最優(yōu)乘車方案,使他在從飯店乘車到使他在從飯店乘車到S公園的過(guò)程公園的過(guò)程 中換車的次數(shù)最少。中換車的次數(shù)最少。 【輸入格式

51、輸入格式】 輸入文件是輸入文件是Travel.in.in。文件的第一行有兩個(gè)數(shù)字。文件的第一行有兩個(gè)數(shù)字M和和N(1=M=100 1N=500），表示開(kāi)通了），表示開(kāi)通了M條單程巴條單程巴 士線路，總共有士線路，總共有N個(gè)車站。從第二行到第個(gè)車站。從第二行到第M刊行依次給出了第刊行依次給出了第1條到第條到第M條巴士線路的信息。其中第條巴士線路的信息。其中第i+1行給出行給出 的是第的是第i條巴士線路的信息，從左至右按運(yùn)行順序依次給出了該線路上的所有站號(hào)相鄰兩個(gè)站號(hào)之間用一個(gè)空條巴士線路的信息，從左至右按運(yùn)行順序依次給出了該線路上的所有站號(hào)相鄰兩個(gè)站號(hào)之間用一個(gè)空 格隔開(kāi)。格隔開(kāi)。 【輸出格式輸

52、出格式】 輸出文件是輸出文件是Travel.out.out，文件只有一行。如果無(wú)法乘巴士從飯店到達(dá)，文件只有一行。如果無(wú)法乘巴士從飯店到達(dá)S公園，則輸出公園，則輸出NO，否則輸出你的，否則輸出你的 程序所找到的最少換車次數(shù)，換車次數(shù)為程序所找到的最少換車次數(shù)，換車次數(shù)為0表示不需換車即可到達(dá)。表示不需換車即可到達(dá)。 【輸入樣例輸入樣例】Travel.in.in 3 7 6 7 4 7 3 6 2 1 3 5 【輸出樣例輸出樣例】Travel.out.out 2 3 3、最短路徑、最短路徑 【問(wèn)題描述問(wèn)題描述】 給出一個(gè)有向圖給出一個(gè)有向圖G=(V, E)，和一個(gè)源點(diǎn)，和一個(gè)源點(diǎn)v0V，請(qǐng)寫(xiě)一個(gè)

53、程序輸出，請(qǐng)寫(xiě)一個(gè)程序輸出v0和圖和圖G中其它頂點(diǎn)的最短中其它頂點(diǎn)的最短 路徑。只要所有的有向環(huán)都是正的，我們就允許圖的邊有負(fù)值。頂點(diǎn)的標(biāo)號(hào)從路徑。只要所有的有向環(huán)都是正的，我們就允許圖的邊有負(fù)值。頂點(diǎn)的標(biāo)號(hào)從1到到n（n為圖為圖G 的頂點(diǎn)數(shù)）。的頂點(diǎn)數(shù)）。 【輸入格式輸入格式】 第第1行：一個(gè)正數(shù)行：一個(gè)正數(shù)n（2=n 2) = 2 (1 - 3) = 5 (1 - 4) = 9 (1 - 5) = 9 樣例所對(duì)應(yīng)的圖如下樣例所對(duì)應(yīng)的圖如下: 第四節(jié) 圖的連通性問(wèn)題 一、判斷圖中的兩點(diǎn)是否連通 1、Floyed算法 時(shí)間復(fù)雜度：O(N3 ) 算法實(shí)現(xiàn)： 把相連的兩點(diǎn)間的距離設(shè)為disij=t

54、rue,不相連的兩點(diǎn)設(shè)為disij=false ，用Floyed算法的變形： for (k = 1; k = n; k+) for (i = 1; i = n; i+) for (j = 1; j = n; j+) disij = disij | (disik 最后如果disij=true的話，那么就說(shuō)明兩點(diǎn)之間有路徑連通。 有向圖與無(wú)向圖都適用。 2、遍歷算法 時(shí)間復(fù)雜度：O(N2 ) 算法實(shí)現(xiàn)： 從任意一個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次遍歷，能夠 從這個(gè)點(diǎn)出發(fā)到達(dá)的點(diǎn)就與起點(diǎn)是聯(lián)通的。這樣 就可以求出此頂點(diǎn)和其它各個(gè)頂點(diǎn)的連通情況。 所以只要把每個(gè)頂點(diǎn)作為出發(fā)點(diǎn)都進(jìn)行一次遍歷 ，就能知道任意兩個(gè)頂點(diǎn)之間是否有路存在。 可以使用DFS實(shí)現(xiàn)。 有向圖與無(wú)向圖都適用。 二、最小環(huán)問(wèn)題 最小環(huán)就是指在一張圖中找出一個(gè)環(huán)，使得這個(gè)環(huán)上的各條邊的權(quán)值之和最小。在 Floyed的同時(shí)，可以順便算出最小環(huán)。 記兩點(diǎn)間的最短路為disij，gij為邊的權(quán)值。 for (k = 1