首页 > 代码库 > 最小生成树（kruskal模版 Prim模板）

最小生成树（kruskal模版 Prim模板）

2024-07-09 16:14:04   222人阅读

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2144&cid=1186

最小生成树，最重要的是了解思想

稠密图用Prim,稀疏图用Kruskal

K（每次找最小的边连接，一条边连接两个点，所以单路就可以了）

 1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 int bin[110]; 5 struct node 6 { 7     int u,v,w; 8 }q[10001]; 9 10 int cmp(const void *a,const void *b)//按距离从小到大排序11 {12     return (*(node *)a).w-(*(node *)b).w;13 }14 int find(int a)15 {16    if(a==bin[a])17    return a;18    else19    bin[a]=find(bin[a]);20 };21 int main()22 {23     int n,m,i,j,sum,num;24     int x,y;25     while(~scanf("%d%d",&n,&m))26     {27         sum=0; num=0;28         for(i=1; i<=n; i++)29         bin[i]=i;30         for(i=0; i<=m-1; i++)31             scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);32         qsort(q,m,sizeof(q[0]),cmp);33      这是重点思想 for(i=0; i<=m-1; i++)34         {35             x=find(q[i].u); y=find(q[i].v);36             if(x!=y)  //检查是否连通37             {38                 sum+=q[i].w;//没连通的话加上距离39                 num++;   //城市+140                 bin[x]=y;41             }42             if(num==n-1)43             break;44         }45         printf("%d\n",sum);46     }47 }

 

Prim()
  1. #include <stdio.h>  
  2. #include <string.h>  
  3. #define N 1000001  
  4. int map[110][110];  
  5. int vis[110];  
  6. int dis[110];  
  7. int n,m;  
  8.   
  9. void prim()  
  10. {  
  11.     int ans=0;  
  12.     int i,j;  
  13.     memset(vis,0,sizeof(vis));   
  14.     memset(dis,0,sizeof(dis));  
  15.     for(i = 1; i <= n; i++)  
  16.         dis[i] = map[1][i];    
  17.     vis[1] = 1;  
  18.     for(i = 1; i <= n-1; i++)  
  19.     {  
  20.         int pos;  
  21.         int min;   
  22.         min = N;  
  23.         for(j = 1; j <= n; j++)  
  24.         {  
  25.             if(vis[j]==0&&min>dis[j])  
  26.             {  
  27.                 pos=j;  
  28.                 min=dis[j];  
  29.             }  
  30.         }  
  31.           
  32.         vis[pos]  = 1;   
  33.         ans += min;      
  34.         for(j = 1; j <= n; j++)    
  35.         {  
  36.             if(vis[j]==0&& dis[j]>map[pos][j])  
  37.                 dis[j]=map[pos][j];  
  38.         }  
  39.     }  
  40.      printf("%d\n",ans);  
  41.      return ;  
  42.   
  43. }  
  44.   
  45. int main()  
  46. {  
  47.     int a,b,c;  
  48.     int i,j;  
  49.     while(scanf("%d %d",&n,&m)!=EOF)  
  50.     {  
  51.   
  52.         for(i=1; i<=n; i++)  
  53.         {  
  54.             for(j=1; j<=n; j++)  
  55.             {  
  56.                 map[i][j]=N;  
  57.                 map[j][i]=N;  
  58.             }   
  59.               map[i][i]=0;  
  60.         }  
  61.         for(i=1;i<=m;i++)  
  62.         {  
  63.             scanf("%d%d%d",&a,&b,&c);  
  64.             if(c<map[a][b])  
  65.             {  
  66.                 map[a][b]=c;  
  67.                 map[b][a]=c;  
  68.             }  
  69.         }  
  70.        prim();  
  71.     }  
  72.     return 0;  
  73. }  

 

 

 


联系
我们