Prim计算最小生成树权值 C语言

标签：空格   测试表   标识   code   使用   要求   fine   无限   定义   

题目描述

现在，你被委托在一个广阔区域里面为某些确定的结点设计连接网络。首先，你会给定在区域里面的一系列结点，和连接这些结点的一组线路。对于每条可能使用的线路，你能得到铺设该线路所需要的线缆长度。需要注意的是，在两个给定的结点之间可能存在许多路径。另外，假设给定的线路必定会连接（直接或间接）该区域里面的2个结点。

你的任务是为该区域设计一个网络，使得该区域中的任意2个结点之间都存在（直接或间接的）连接（也就是说，所有给定的结点之间都是连通的，但不一定存在直接相连的线路），同时，使得铺设该网络的线缆总长度最小。

输入格式

输入由多个测试构成。每个测试定义一个要求的网络。每个测试的第一个包含2个整数：第一个整数P给定区域内结点的数目，第二个整数R给出了线路的数目。接下来的R行，给出了两个结点之间的线路，每行包含3个整数：前2个数字表示线路连接的结点，第三个整数表示铺设该线路需要的线缆长度。每个整数之间用一个空格隔开。只给出一个整数P=0的测试表示输入结束。每个测试之间用一个空行隔开。

输入的最大的结点数目是50。给定的线路的最大长度是100。但是，可能存在的线路数目是无限的。给定的结点由整数1~P来标识（包含P）。需要注意，结点i和j之间的线路可能由i到j的线路来表示，也可能由j到i的线路来表示。

输出格式

对于每一个测试，在单独的一行输出一个数字，表示为铺设整个网络所需要的线缆总长度。

样例输入

1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

样例输出

0
17
16
26

分析

即计算最小生成树的权值（相关知识：Prim算法和 Kruskal算法）

代码实现

#include 
#define MAXVERTEX 52
#define MAXEDGE 102
#define INF 1e7 

//prim算法计算最小生成树的权值 
int Prim(int matrix[][MAXVERTEX],int vnum, int ednum){
	int mst = 0;
	int isIntree[vnum+1] ;
	for(int i = 0; i 

Prim计算最小生成树权值 C语言

标签：空格   测试表   标识   code   使用   要求   fine   无限   定义   

原文地址：https://www.cnblogs.com/miaomiaolan/p/12852631.html