模板--最小生成树【prim】

逃离我推掉我的手 2022-06-11 01:11 192阅读 0赞

问题描述：   
  
有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。  
  
 输入：

输入包含多组数据，格式如下。  
第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)  
剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

输出：

每组输出占一行，仅输出最小花费。

样例输入：

3 2  
1 2 1  
1 3 1  
1 0

样例输出：

2  
0

代码：

#include <stdio.h> 
    #include <string.h> 
    #include <stdlib.h> 
    #include <algorithm> 
    #define INF 0x3f3f3f3f 
     using namespace std;  
    int arr[110][110];  
     int dis[110];//用来记录当前生成树到每个节点的距离 
     bool vis[110];//标记数组 
    int prim(int n)  
     {  
         memset(vis,false,sizeof(vis));//标记数组清零 
         for(int i=1; i<=n; i++)  
         {  
             dis[i] = arr[1][i];//从1号节点开始生成树 
         }  
         int ans = 0;//距离权值总和 
         vis[1] = true;//生成树的根（起点）标记访问过 
         for(int i=2; i<=n; i++)//要生成n-1条边，所以循环n-1次 
         {  
             int pos = i;//用来记录每一次循环找到的节点编号 
             int Min = INF;//无穷大 
             for(int j=1; j<=n; j++)//对dis数组进行遍历找到距离最小的 
             {  
                 if(vis[j]==false && dis[j] < Min)//如果该点未被访问过，并且距离更小 
                 {  
                     Min = dis[j];//更新最小距离 
                     pos = j;//记录节点编号 
                 }  
             }  
             ans += Min;//加上找到的最小权值 
             vis[pos] = true;//标记找到的该点被访问 
             for(int j=1; j<=n; j++)//更新dis数组 
             {  
                 if(vis[j]==false && dis[j] > arr[pos][j])//如果该点未被访问过且距离更大 
                 {  
                     dis[j] = arr[pos][j];//更新生成树到该点的距离 
                 }  
             }  
         }  
         return ans;//得出权值总和 
     }  
     int main()  
     {  
         int n,m;  
         while(~scanf("%d %d",&n,&m))  
         {  
             for(int i=1; i<=n; i++)  
                 for(int j=1; j<=n; j++)  
                     i==j?arr[i][j]=0:arr[i][j]=INF;//无穷大 
             for(int i=0,u,v,w; i<m; i++)  
             {  
                 scanf("%d %d %d",&u,&v,&w);  
                 if(arr[u][v] > w)  
                     arr[u][v] = arr[v][u] = w;  
             }  
             printf("%d\n",prim(n));  
         }  
         return 0;  
     }