?ps(我到今天才知道Floyd的核心思想是動態規劃==）

hdu?1599?find?the?mincost?route（找無向圖最小環）

?

注意！這里寫成???#define?data?0x3f3f3f3f??memset(map,data,sizeof(map))是wrong?按理來說應該不錯，郁悶，以后還是循環賦值然后宏定義#define?data?100000000
Problem?Description

杭州有N個景區，景區之間有一些雙向的路來連接，現在8600想找一條旅游路線，這個路線從A點出發并且最后回到A點，假設經過的路線為V1,V2,....VK,V1,那么必須滿足K>2,就是說至除了出發點以外至少要經過2個其他不同的景區，而且不能重復經過同一個景區。現在8600需要你幫他找一條這樣的路線，并且花費越少越好。

?

Input

第一行是2個整數N和M（N?<=?100,?M?<=?1000)，代表景區的個數和道路的條數。
接下來的M行里，每行包括3個整數a,b,c.代表a和b之間有一條通路，并且需要花費c元(c?<=?100)。

?

Output

對于每個測試實例，如果能找到這樣一條路線的話，輸出花費的最小值。如果找不到的話，輸出"It's?impossible.".

?

Sample?Input

3?3?1?2?1?2?3?1?1?3?1?3?3?1?2?1?1?2?3?2?3?1

?

Sample?Output

3?It's?impossible.

??對于找最小環，而且要經過至少兩個節點，權值和最小，算法是floyd，但該注意和理解的地方實在很多

???1.定義和理解：轉自http://leon.cc.blogbus.com/logs/3629782.html
????在圖論中經常會遇到這樣的問題，在一個有向圖里，求出任意兩個節點之間的最短距離。我們在離散數學、數據結構課上都遇到過這個問題，在計算機網絡里介紹網絡層的時候好像也遇到過這個問題，記不請了...?但是書本上一律采取的是Dijkstra算法，通過Dijkstra算法可以求出單源最短路徑，然后逐個節點利用Dijkstra算法就可以了。不過在這里想換換口味，采取Robert?Floyd提出的算法來解決這個問題。下面讓我們先把問題稍微的形式化一下：
?????如果有一個矩陣D=[d(ij)]，其中d(ij)>0表示i城市到j城市的距離。若i與j之間無路可通，那么d(ij)就是無窮大。又有d(ii)=0。編寫一個程序，通過這個距離矩陣D，把任意兩個城市之間的最短與其行徑的路徑找出來。
?????我們可以將問題分解，先找出最短的距離，然后在考慮如何找出對應的行進路線。如何找出最短路徑呢，這里還是用到動態規劃的知識，對于任何一個城市而言，i到j的最短距離不外乎存在經過i與j之間的k和不經過k兩種可能，所以可以令k=1，2，3，...，n(n是城市的數目)，在檢查d(ij)與d(ik)+d(kj)的值；在此d(ik)與d(kj)分別是目前為止所知道的i到k與k到j的最短距離，因此d(ik)+d(kj)就是i到j經過k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發經過k再到j的距離要比原來的i到j距離短，自然把i到j的d(ij)重寫為d(ik)+d(kj)，每當一個k查完了，d(ij)就是目前的i到j的最短距離。重復這一過程，最后當查完所有的k時，d(ij)里面存放的就是i到j之間的最短距離了。所以我們就可以用三個for循環把問題搞定了，但是有一個問題需要注意，那就是for循環的嵌套的順序：我們可能隨手就會寫出這樣的程序，但是仔細考慮的話，會發現是有問題的。

?????????????????????for(int?i=0;?i<n;?i++)
???????????????????????????for(int?j=0;?j<n;?j++)
????????????????????????????????for(int?k=0;?k<n;?k++)???
????

?????問題出在我們太早的把i-k-j的距離確定下來了，假設一旦找到了i-p-j最短的距離后，i到j就相當處理完了，以后不會在改變了，一旦以后有使i到j的更短的距離時也不能再去更新了，所以結果一定是不對的。所以應當象下面一樣來寫程序：

???????????????????for(int?k=0;?k<n;?k++)
?????????????????????????for(int?i=0;?i<n;?i++)
??????????????????????????????for(int?j=0;?j<n;?j++)

????這樣作的意義在于固定了k，把所有i到j而經過k的距離找出來，然后象開頭所提到的那樣進行比較和重寫，因為k是在最外層的，所以會把所有的i到j都處理完后，才會移動到下一個k，這樣就不會有問題了，看來多層循環的時候，我們一定要當心，否則很容易就弄錯了。
?????接下來就要看一看如何找出最短路徑所行經的城市了，這里要用到另一個矩陣P，它的定義是這樣的：p(ij)的值如果為p，就表示i到j的最短行經為i->...->p->j，也就是說p是i到j的最短行徑中的j之前的最后一個城市。P矩陣的初值為p(ij)=i。有了這個矩陣之后，要找最短路徑就輕而易舉了。對于i到j而言找出p(ij)，令為p，就知道了路徑i->...->p->j；再去找p(ip)，如果值為q，i到p的最短路徑為i->...->q->p；再去找p(iq)，如果值為r，i到q的最短路徑為i->...->r->q；所以一再反復，到了某個p(it)的值為i時，就表示i到t的最短路徑為i->t，就會的到答案了，i到j的最短行徑為i->t->...->q->p->j。因為上述的算法是從終點到起點的順序找出來的，所以輸出的時候要把它倒過來。
?????但是，如何動態的回填P矩陣的值呢？回想一下，當d(ij)>d(ik)+d(kj)時，就要讓i到j的最短路徑改為走i->...->k->...->j這一條路，但是d(kj)的值是已知的，換句話說，就是k->...->j這條路是已知的，所以k->...->j這條路上j的上一個城市(即p(kj))也是已知的，當然，因為要改走i->...->k->...->j這一條路，j的上一個城市正好是p(kj)。所以一旦發現d(ij)>d(ik)+d(kj)，就把p(kj)存入p(ij)。

?

?2?對于代碼的理解：

?

[cpp]?view?plaincopyprint?

1?#include<iostream>??

2?#include<cstdio>??

3?#include<cstring>??

4?using?namespace?std;??

5?#define?data?100000000??

6?#define?N?110??

7?#define?min(x,y)?((x)>(y)?(y):(x))??

8?int?map[N][N],dis[N][N];??

9?int?n,m;??

10?void?floyd()??

11?{??

12?????int?i,j,k,mina=data;??

13?????for(k=1;k<=n;k++)??

14?????{??

15?????//因為路徑i到j的情況只有經過k和不經過k，而要求從一個點至少經過兩個節點返回原點，k每次更新都會使dis[i][j]得到更新，而只有在更新了一次k之后才可以找min，min即是在dis[i][i]最短的情況下的求至少經過兩個點又回到該點的最小距離，所以i和j的值都應該小于k，i的值從1到k-1，而j的值卻跟i的值相關，即i!=j，因為當i=j時，dis[i][j]不是無窮大，而是從i->j->i的值，這就會出現自環，這里我定義自環為經過一個節點就返回原節點的節點，比如像1->2->1這樣min的值會不準確，這不是經過了兩個節點,所以下面第一個兩層循環可以有三種寫法，具體看代碼??

16???

17?//當要擴充第k個節點時，前k-1個節點已經用過，并且是用于更新最短路徑dis[i][j]這就是第二個兩層for循環，所以在更新k之前已經有一條最短路徑從i到達j，此時再來尋找另外一個從i到j的路徑，map[j][k]+map[k][i]，如果有的話則一定形成了從i回到i的環，比如?1->2值為1，2->3值為2,3->4值為3,4->1值為4，則第一次存在從1到3的最短路，再尋找時找到了1到4,4到3的路徑，則形成了環，而且是最小的，注意第一個循環中加上的值是map[j][k]和map[k][i]的值，map的是值都是初始值，不會變化，而dis在不斷更新??

18?????????for(i=1;i<k;i++)??

19?????????{??

20?????????????for(j=i+1;j<k;j++)??

21?????????????{??

22?????????????????mina=min(dis[i][j]+map[j][k]+map[k][i],mina);??

23?????????????}??

24?????????}??

25?????????for(i=1;i<=n;i++)??

26?????????{??

27?????????????for(j=1;j<=n;j++)??

28?????????????{??

29????????????????if(dis[i][j]>(dis[i][k]+dis[k][j]))??

30?????????????????dis[i][j]=dis[i][k]+dis[k][j];??

31?????????????}??

32?????????}??

33?????}??

34?????if(mina<data)??

35?????printf("%d\n",mina);??

36?????else??

37?????printf("It's?impossible.\n");??

38?}??

39?int?main()??

40?{??

41?????int?a,b,c,i,j;??

42?????while(scanf("%d%d",&n,&m)!=EOF)??

43?????{??

44?????????for(i=0;i<=n;i++)??

45??????????for(j=0;j<=n;j++)??

46??????????{??

47??????????????map[i][j]=data;??

48??????????????dis[i][j]=data;??

49??????????}??

50?????????for(i=0;i<m;i++)??

51?????????{??

52?????????????scanf("%d%d%d",&a,&b,&c);??

53?????????????if(map[a][b]>c)??

54?????????????{??

55??????????????????map[a][b]=map[b][a]=c;??

56??????????????????dis[a][b]=dis[b][a]=c;??

57?????????????}??

58?????????}??

59?????????floyd();??

60?????}??

61?????return?0;??

62?}??

這是第二種：

[cpp]?view?plaincopyprint?

63?#include<iostream>??

64?#include<cstdio>??

65?#include<cstring>??

66?using?namespace?std;??

67?#define?data?100000000??

68?#define?N?110??

69?#define?min(x,y)?((x)>(y)?(y):(x))??

70?int?map[N][N],dis[N][N];??

71?int?n,m;??

72?void?floyd()??

73?{??

74?????int?i,j,k,mina=data;??

75?????for(k=1;k<=n;k++)??

76?????{??

77?????????for(i=1;i<k;i++)??

78?????????{??

79?????????????for(j=1;j<i;j++)??

80?????????????{??

81?????????????????mina=min(dis[i][j]+map[j][k]+map[k][i],mina);??

82?????????????}??

83?????????}??

84?????????for(i=1;i<=n;i++)??

85?????????{??

86?????????????for(j=1;j<=n;j++)??

87?????????????{??

88????????????????if(dis[i][j]>(dis[i][k]+dis[k][j]))??

89?????????????????dis[i][j]=dis[i][k]+dis[k][j];??

90?????????????}??

91?????????}??

92?????}??

93?????if(mina<data)??

94?????printf("%d\n",mina);??

95?????else??

96?????printf("It's?impossible.\n");??

97?}??

98?int?main()??

99?{??

100?????int?a,b,c,i,j;??

101?????while(scanf("%d%d",&n,&m)!=EOF)??

102?????{??

103?????????for(i=0;i<=n;i++)??

104??????????for(j=0;j<=n;j++)??

105??????????{??

106??????????????map[i][j]=data;??

107??????????????dis[i][j]=data;??

108??????????}??

109?????????for(i=0;i<m;i++)??

110?????????{??

111?????????????scanf("%d%d%d",&a,&b,&c);??

112?????????????if(map[a][b]>c)??

113?????????????{??

114??????????????????map[a][b]=map[b][a]=c;??

115??????????????????dis[a][b]=dis[b][a]=c;??

116?????????????}??

117?????????}??

118?????????floyd();??

119?????}??

120?????return?0;??

121?}??

這是第三種：

[cpp]?view?plaincopyprint?

122?#include<iostream>??

123?#include<cstdio>??

124?#include<cstring>??

125?using?namespace?std;??

126?#define?data?100000000??

127?#define?N?110??

128?#define?min(x,y)?((x)>(y)?(y):(x))??

129?int?map[N][N],dis[N][N];??

130?int?n,m;??

131?void?floyd()??

132?{??

133?????int?i,j,k,mina=data;??

134?????for(k=1;k<=n;k++)??

135?????{??

136?????????for(i=1;i<k;i++)??

137?????????{??

138?????????????for(j=1;j<k;j++)??

139?????????????{??

140?????????????????mina=min(dis[i][j]+map[j][k]+map[k][i],mina);??

141?????????????}??

142?????????}??

143?????????for(i=1;i<=n;i++)??

144?????????{??

145?????????????for(j=1;j<=n;j++)??

146?????????????{??

147??????????????//注意這里i!=j???

148????????????????if(i!=j&&dis[i][j]>(dis[i][k]+dis[k][j]))??

149?????????????????dis[i][j]=dis[i][k]+dis[k][j];??

150?????????????}??

151?????????}??

152?????}??

153?????if(mina<data)??

154?????printf("%d\n",mina);??

155?????else??

156?????printf("It's?impossible.\n");??

157?}??

158?int?main()??

159?{??

160?????int?a,b,c,i,j;??

161?????while(scanf("%d%d",&n,&m)!=EOF)??

162?????{??

163?????????for(i=0;i<=n;i++)??

164??????????for(j=0;j<=n;j++)??

165??????????{??

166??????????????map[i][j]=data;??

167??????????????dis[i][j]=data;??

168??????????}????

169?????????for(i=0;i<m;i++)??

170?????????{??

171?????????????scanf("%d%d%d",&a,&b,&c);??

172?????????????if(map[a][b]>c)??

173?????????????{??

174??????????????????map[a][b]=map[b][a]=c;??

175??????????????????dis[a][b]=dis[b][a]=c;??

176?????????????}?????

177?????????}??

Floyd算法

正如我們所知道的，Floyd算法用于求最短路徑。Floyd算法可以說是Warshall算法的擴展，三個for循環就可以解決問題，所以它的時間復雜度為O(n^3)。

Floyd算法的基本思想如下：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點X到B。所以，我們假設Dis(AB)為節點A到節點B的最短路徑的距離，對于每一個節點X，我們檢查Dis(AX)?+?Dis(XB)?<?Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設置Dis(AB)?=?Dis(AX)?+?Dis(XB)，這樣一來，當我們遍歷完所有節點X，Dis(AB)中記錄的便是A到B的最短路徑的距離。

很簡單吧，代碼看起來可能像下面這樣：

?

for(inti?=?0;?i?<?節點個數;?++i?) { for(intj?=?0;?j?<?節點個數;?++j?) { for(intk?=?0;?k?<?節點個數;?++k?) { if(?Dis[i][k]?+?Dis[k][j]?<?Dis[i][j]?) { //?找到更短路徑 Dis[i][j]?=?Dis[i][k]?+?Dis[k][j]; } } } }

但是這里我們要注意循環的嵌套順序，如果把檢查所有節點X放在最內層，那么結果將是不正確的，為什么呢？因為這樣便過早的把i到j的最短路徑確定下來了，而當后面存在更短的路徑時，已經不再會更新了。

讓我們來看一個例子，看下圖：

圖中紅色的數字代表邊的權重。如果我們在最內層檢查所有節點X，那么對于A->B，我們只能發現一條路徑，就是A->B，路徑距離為9。而這顯然是不正確的，真實的最短路徑是A->D->C->B，路徑距離為6。造成錯誤的原因就是我們把檢查所有節點X放在最內層，造成過早的把A到B的最短路徑確定下來了，當確定A->B的最短路徑時Dis(AC)尚未被計算。所以，我們需要改寫循環順序，如下：

?

for(intk?=?0;?k?<?節點個數;?++k?) { for(inti?=?0;?i?<?節點個數;?++i?) { for(intj?=?0;?j?<?節點個數;?++j?) { if(?Dis[i][k]?+?Dis[k][j]?<?Dis[i][j]?) { //?找到更短路徑 Dis[i][j]?=?Dis[i][k]?+?Dis[k][j]; } } } }

這樣一來，對于每一個節點X，我們都會把所有的i到j處理完畢后才繼續檢查下一個節點。

那么接下來的問題就是，我們如何找出最短路徑呢？這里需要借助一個輔助數組Path，它是這樣使用的：Path(AB)的值如果為P，則表示A節點到B節點的最短路徑是A->...->P->B。這樣一來，假設我們要找A->B的最短路徑，那么就依次查找，假設Path(AB)的值為P，那么接著查找Path(AP)，假設Path(AP)的值為L，那么接著查找Path(AL)，假設Path(AL)的值為A，則查找結束，最短路徑為A->L->P->B。

那么，如何填充Path的值呢？很簡單，當我們發現Dis(AX)?+?Dis(XB)?<?Dis(AB)成立時，就要把最短路徑改為A->...->X->...->B，而此時，Path(XB)的值是已知的，所以，Path(AB)?=?Path(XB)。

好了，基本的介紹完成了，接下來就是實現的時候了，這里我們使用圖以及鄰接矩陣：

?

#define?INFINITE?1000?//?最大值 #define?MAX_VERTEX_COUNT?20?　　//?最大頂點個數 // structGraph { intarrArcs[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];//?鄰接矩陣 intnVertexCount;?　　//?頂點數量 intnArcCount;?　　//?邊的數量 }; //

首先，我們寫一個方法，用于讀入圖的數據：

?

voidreadGraphData(?Graph?*_pGraph?) { std::cout?<<"請輸入頂點數量和邊的數量:?"; std::cin?>>?_pGraph->nVertexCount; std::cin?>>?_pGraph->nArcCount; std::cout?<<"請輸入鄰接矩陣數據:"<<?std::endl; for(introw?=?0;?row?<?_pGraph->nVertexCount;?++row?) { for(intcol?=?0;?col?<?_pGraph->nVertexCount;?++col?) { std::cin?>>?_pGraph->arrArcs[row][col]; } } }

接著，就是核心的Floyd算法：

?

voidfloyd(int_arrDis[][MAX_VERTEX_COUNT],int_arrPath[][MAX_VERTEX_COUNT],int_nVertexCount?) { //?先初始化_arrPath for(inti?=?0;?i?<?_nVertexCount;?++i?) { for(intj?=?0;?j?<?_nVertexCount;?++j?) { _arrPath[i][j]?=?i; } } // for(intk?=?0;?k?<?_nVertexCount;?++k?) { for(inti?=?0;?i?<?_nVertexCount;?++i?) { for(intj?=?0;?j?<?_nVertexCount;?++j?) { if(?_arrDis[i][k]?+?_arrDis[k][j]?<?_arrDis[i][j]?) { //?找到更短路徑 _arrDis[i][j]?=?_arrDis[i][k]?+?_arrDis[k][j]; _arrPath[i][j]?=?_arrPath[k][j]; } } } } }

OK，最后是輸出結果數據代碼：

?

voidprintResult(int_arrDis[][MAX_VERTEX_COUNT],int_arrPath[][MAX_VERTEX_COUNT],int_nVertexCount?) { std::cout?<<"Origin?->?Dest?Distance?Path"<<?std::endl; for(inti?=?0;?i?<?_nVertexCount;?++i?) { for(intj?=?0;?j?<?_nVertexCount;?++j?) { if(?i?!=?j?)//?節點不是自身 { std::cout?<<?i+1?<<"?->?"<<?j+1?<<"\t\t"; if(?INFINITE?==?_arrDis[i][j]?)//?i?->?j?不存在路徑 { std::cout?<<"INFINITE"<<"\t\t"; } else { std::cout?<<?_arrDis[i][j]?<<"\t\t"; //?由于我們查詢最短路徑是從后往前插，因此我們把查詢得到的節點 //?壓入棧中，最后彈出以順序輸出結果。 std::stack<int>?stackVertices; intk?=?j; do { k?=?_arrPath[i][k]; stackVertices.push(?k?); }while(?k?!=?i?); // std::cout?<<?stackVertices.top()+1; stackVertices.pop(); unsignedintnLength?=?stackVertices.size(); for(?unsignedintnIndex?=?0;?nIndex?<?nLength;?++nIndex?) { std::cout?<<"?->?"<<?stackVertices.top()+1; stackVertices.pop(); } std::cout?<<"?->?"<<?j+1?<<?std::endl; } } } } }

好了，是時候測試了，我們用的圖如下：

測試代碼如下：

?

intmain(void) { Graph?myGraph; readGraphData(?&myGraph?); // intarrDis[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; intarrPath[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; //?先初始化arrDis for(inti?=?0;?i?<?myGraph.nVertexCount;?++i?) { for(intj?=?0;?j?<?myGraph.nVertexCount;?++j?) { arrDis[i][j]?=?myGraph.arrArcs[i][j]; } } floyd(?arrDis,?arrPath,?myGraph.nVertexCount?); // printResult(?arrDis,?arrPath,?myGraph.nVertexCount?); // system("pause"); return0; }

如圖：

?

?

?

#include<stdio.h>
#define inf 99999999
#define Min(a,b)((a)<(b))?(a):(b)
int n,m,min;
int d[102][102];
int a[102][102];
void floyd()
{
??? int i,k,j;
??? min=inf;
??? for(k=1;k<=n;k++)
??? {
??????? for(i=1;i<k;i++)
??????????? for(j=1;j<i;j++)
???????????????? min=Min(min,d[i][j]+a[i][k]+a[k][j]);
??????? for(i=1;i<=n;i++)
??????????? for(j=1;j<=n;j++)
??????????????? d[i][j]=Min(d[i][j],d[i][k]+d[k][j]);
??? }
}
int main()
{
??? int p,q,i,j,len;
??? while(scanf("%d%d",&n,&m)!=EOF)
??? {
??????? for(i=1;i<=n;i++)
?????????? for(j=1;j<=n;j++)
????????????? a[i][j]=inf;
??????? for(i=1;i<=m;i++)
??????? {
??????????? scanf("%d%d%d",&p,&q,&len);
??????????? if(len<a[p][q])
????????????? a[p][q]=a[q][p]=len;
??????? }
??????? for(i=1;i<=n;i++)
??????????? for(j=1;j<=n;j++)
??????????????? d[i][j]=a[i][j];
??????? floyd();
??????? if(min!=inf)
??????????? printf("%d\n",min);
??????? else?
?? printf("It's impossible.\n");
??? }
??? return 0;
}

總結

以上是生活随笔為你收集整理的hdu 1599 find the mincost route（找无向图最小环）（floyd求最小环）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。