Highways?

大意：給你一個(gè)用鄰接矩陣形式存儲(chǔ)的有n個(gè)頂點(diǎn)的無(wú)向圖，讓你求它的最小生成樹并求出在這個(gè)生成樹里面最大的邊的權(quán)值。

思路：用Prim求，判斷條件改一下就行。

PS：dis數(shù)組初始化的時(shí)候用memset一直RE，希望有知道怎么回事的不吝賜教，謝了~

? 1 #include <stdio.h> 2 #include <string.h> 3 #define INF 0x3f3f3f3f 4 5 int Map[510][510]; 6 int dis[510]; 7 int n, m; 8 9 int min(int a, int b) 10 { 11 return a > b ? b : a; 12 } 13 14 int Prim() 15 { 16 int Min_ele, Min_node; 17 for(int i = 1; i <= n; i++) 18 { 19 dis[i] = INF; 20 } 21 ///這里如果用memset(dis, INF, sizeof(dis));的話會(huì)一直RE 22 int r = 1; 23 int Ans = 0; 24 for(int i = 1; i < n; i++) 25 { 26 Min_ele = INF; 27 dis[r] = -1; 28 for(int j = 1; j <= n; j++) 29 { 30 if(j != r && dis[j] >= 0) 31 { 32 dis[j] = min(dis[j], Map[r][j]); 33 if(dis[j] < Min_ele) 34 { 35 Min_ele = dis[j]; 36 Min_node = j; 37 } 38 } 39 } 40 r = Min_node; 41 if(Min_ele > Ans) 42 Ans = Min_ele; 43 } 44 return Ans; 45 } 46 47 void Solve() 48 { 49 scanf("%d", &m); 50 while(m--) 51 { 52 scanf("%d", &n); 53 memset(Map, 0, sizeof(Map)); 54 for(int i = 1; i <= n; i++) 55 { 56 for(int j = 1; j <= n; j++) 57 { 58 scanf("%d", &Map[i][j]); 59 } 60 } 61 printf("%d\n", Prim()); 62 } 63 } 64 65 int main() 66 { 67 Solve(); 68 69 return 0; 70 } Highways

?

轉(zhuǎn)載于:https://www.cnblogs.com/Silence-AC/p/3531342.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2485 Highways（最小生成树 Prim）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。