数据结构实验之图论九：最小生成树

雨点打透心脏的1/2处 2022-12-23 07:21 109阅读 0赞

## 数据结构实验之图论九：最小生成树 ##

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

Input  
输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)

剩下m行每行3个非负整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c（城市编号从1到n）。

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

Sample  
Input  
3 2  
1 2 1  
1 3 1  
1 0  
Output  
2  
0  
*这个题目和通公路那一题思路是差不多的，不过要注意几个点，首先是，最小生成树的边数不可能小于节点数减1，另外这题目的数据有一些坑点，就是后台的数据可能有的数据是无穷大，所以在输入的时候要判断一下是不是小于INF，小于的话才将权值记录。*

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define inf 0x3f3f3f3f
    int map[1100][1100], vis[1100], lowcost[1100];
    int n, flag,sum;
    void prime()
    {
        
    	int k, temp,i,j;
    	vis[1] = 1;
    	for (i = 1; i <= n; i++)
    		lowcost[i] = map[i][1];
    	for (i = 2; i <= n; i++)
    	{
        
    		temp = inf;
    		for (j = 1; j <= n; j++)
    		{
        
    			if (vis[j] == 0 && lowcost[j] < temp)
    			{
        
    				k = j;
    				temp = lowcost[j];
    			}
    		}
    		if (temp == inf)
    		{
        
    			flag = 0;
    			break;
    		}
    		vis[k] = 1;
    		sum += temp;
    		for (j = 1; j <= n; j++)
    		{
        
    			if (vis[j] == 0 && lowcost[j] > map[k][j])
    				lowcost[j] = map[k][j];
    		}
    	}
    }
    int main()
    {
        
    	int m, i;
    	while (~scanf("%d %d", &n, &m))
    	{
        
    		memset(vis, 0, sizeof(vis));
    		memset(lowcost, 0, sizeof(lowcost));
    		memset(map, inf, sizeof(map));
    		for (i = 1; i <= n; i++)
    			map[i][i] = 0;
    		for (i = 0; i < m; i++)
    		{
        
    			int a, b, c;
    			scanf("%d %d %d", &a, &b, &c);
    			if(c<map[a][b])//输入的时候注意判断该数是不是小于两点的理论路径的最大值
    			map[a][b] = map[b][a] = c;
    		}
    		flag = 1;
    		sum = 0;
    		prime();
    		if (m < n - 1)
    			printf("0\n");
    		if (flag)
    			printf("%d\n", sum);
    	}
    }

*详细注释可见[数据结构实验之图论六：村村通公路][Link 1]*

[Link 1]: https://blog.csdn.net/qq_45885219/article/details/109909031