思路：

　　比較典型的最小生成樹的題目了、、在這里用求最小生成樹的經典算法K(Kruskal)算法和P（Prim）算法。我的 K 算法用的是結構體來存圖，P 算法用的是鄰接矩陣來存圖，K算法的復雜度是O(ElogE)，比較適用于稀疏圖，P算法的復雜的是O（V ^ 2）,適合用稠密圖。

以下是C++的K算法代碼

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 using namespace std; 9 10 const int MAXN = 2e3+ 3; 11 int pre[MAXN]; 12 int m,n; 13 14 int Find(int x) //并查集 15 { 16 return x == pre[x] ? x :(pre[x] = Find(pre[x])); 17 } 18 19 struct Node //存圖 20 { 21 int u, v, w; 22 }cy[103]; 23 24 int mycmp(Node a,Node b) 25 { 26 return a.w < b.w; 27 } 28 29 void mst() 30 { 31 for(int i = 0 ; i < 102; i++) 32 pre[i] = i; 33 } 34 35 int kru()//算法的具體實現 36 { 37 int ans = 0; 38 int cnt = 0; 39 for(int i = 1; i <= n; i++) 40 { 41 int fv = Find(cy[i].v); 42 int fu = Find(cy[i].u); 43 if(fv != fu) 44 { 45 pre[fv] = fu; 46 ans += cy[i].w; 47 cnt ++; 48 } 49 if(cnt == m -1) 50 { 51 return ans; 52 break; 53 } 54 } 55 return -1; 56 } 57 58 int main() 59 { 60 //freopen("in.cpp","r",stdin); 61 while(~scanf("%d%d",&n,&m) && n) 62 { 63 mst(); 64 for(int i = 1; i <= n; i++) 65 scanf("%d%d%d",&cy[i].u, &cy[i].v, &cy[i].w); 66 sort(cy + 1, cy + n + 1, mycmp); 67 int ans = kru(); 68 if(ans != -1) 69 printf("%d\n",ans); 70 else 71 printf("?\n"); 72 } 73 return 0; 74 }

?

以下是C++的P算法代碼

?

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 using namespace std; 9 10 const int MAXN = 103; 11 const int INF = 0x3f3f3f3f; 12 int edge[MAXN][MAXN]; //用于存放圖 13 int used[MAXN];//用于標記點是否已加入到最小生成樹那個的集合中 14 int lowcost[MAXN]; //用于存放集合外的點到集合內的點的最短距離，每加入一個點需要更新一次 15 int N,M; 16 17 int prim(int start,int maxn) //利用prim算法計算最小生成樹 18 { 19 memset(used, 0, sizeof(used)); 20 for(int i = 1; i <= maxn; i++) 21 { 22 lowcost[i] = edge[start][i]; 23 } 24 used[start] = 1; 25 int sumweight = 0; 26 int ok = 0; 27 for(int i = 1; i <= maxn; i++) 28 { 29 int minn = INF ; 30 int v = -1; 31 for(int j = 1; j <= maxn; j++) 32 { 33 if(used[j] == 0 && lowcost[j] < minn) 34 { 35 minn = lowcost[j]; 36 v = j; 37 } 38 } 39 //cout << v << " "; 40 if(v != -1) 41 { 42 ok++; 43 used[v] = 1; 44 sumweight += lowcost[v]; 45 for(int j = 1; j <= maxn; j++) 46 { 47 if(used[j] == 0 && lowcost[j] > edge[v][j]) 48 { 49 lowcost[j] = edge[v][j]; 50 } 51 } 52 } 53 } 54 if(ok == maxn -1) 55 return sumweight; 56 return -1; 57 } 58 59 int main() 60 { 61 while(cin >> N >> M && N) 62 { 63 memset(edge, 0x3f, sizeof(edge)); 64 while(N--) 65 { 66 int u, v, w; 67 cin >> u >> v >> w; 68 edge[u][v] = edge[v][u] = w; 69 } 70 int ans = prim(1, M); 71 if(ans < 0) cout << "?" <<endl; 72 else cout << ans << endl; 73 } 74 return 0; 75 }

?

以下是JAVA的K算法

?

1 import java.util.Scanner; 2 import java.util.Comparator; 3 import java.util.Arrays; 4 import java.text.DecimalFormat; 5 6 class Vge{ 7 int u; 8 int v; 9 int w; 10 } 11 12 class mycmp implements Comparator<Vge>{ 13 public int compare( Vge A, Vge B ){ 14 if( A.w - B.w != 0 ) 15 return A.w - B.w; 16 else 17 return A.w - B.w; 18 } 19 } 20 21 public class Main{ 22 final static int MAXN = 100 + 3; 23 static int[] pre = new int[ MAXN ]; 24 static Vge[] clg = new Vge[ MAXN * MAXN ]; 25 public static void main( String[] args ){ 26 Scanner sc = new Scanner( System.in ); 27 int n, m; 28 while( sc.hasNextInt() ){ 29 n = sc.nextInt(); 30 m = sc.nextInt(); 31 if( n == 0 ) break; 32 for( int i = 0; i < n; i++ ){ 33 clg[ i ] = new Vge(); 34 clg[ i ].u = sc.nextInt(); 35 clg[ i ].v = sc.nextInt(); 36 clg[ i ].w = sc.nextInt(); 37 } 38 mst( m ); 39 int ans = ksu( n, m ); 40 if( ans == -1 ) System.out.println( "?" ); 41 else System.out.println( ans ); 42 } 43 sc.close(); 44 } 45 public static void mst( int n ){ 46 for( int i = 0; i <= n; i++ ){ 47 pre[i] = i; 48 } 49 } 50 public static int find( int x ){ 51 return x == pre[ x ] ? x : ( pre[ x ] = find( pre[ x ] ) ); 52 } 53 public static int ksu( int n, int m ){ 54 Arrays.sort( clg, 0, n, new mycmp() ); 55 int cnt = 0; 56 int ans = 0; 57 for( int i = 0; i < n; i++ ){ 58 int fu = find( clg[ i ].u ); 59 int fv = find( clg[ i ].v ); 60 if( fu != fv ){ 61 ans += clg[i].w; 62 cnt ++; 63 pre [ fv ] = fu; 64 } 65 if( cnt == m - 1 ) return ans; 66 } 67 return -1; 68 } 69 }

轉載于:https://www.cnblogs.com/Ash-ly/p/5397646.html

總結

以上是生活随笔為你收集整理的HDU 1863 畅通工程 最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

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