欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-07-02 15:28:50
题目描述 现在,你被委托在一个广阔区域里面为某些确定的结点设计连接网络。首先,你会给定在区域里面的一系列结点,和连接这些结点的一组线路。对于每条可能使用的线路,你能得到铺设该线路所需要的线缆长度。需要注意的是,在两个给定的结点之间可能存在许多路径。另外,假设给定的线路必定会连接(直接或间接)该区域里 ......

题目描述

现在,你被委托在一个广阔区域里面为某些确定的结点设计连接网络。首先,你会给定在区域里面的一系列结点,和连接这些结点的一组线路。对于每条可能使用的线路,你能得到铺设该线路所需要的线缆长度。需要注意的是,在两个给定的结点之间可能存在许多路径。另外,假设给定的线路必定会连接(直接或间接)该区域里面的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 <stdio.h>
#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 < vnum+1; i++)isintree[i] = 0;
	isintree[1] = 1; //设置一个初始点
    //遍历vnum-1次,找出vnum-1个点
	for(int i = 0; i < vnum-1; i++){
		int min = inf;
		int temp1,temp2;
		for(int j = 1; j <= vnum; j ++){
			for(int k = j+1; k <= vnum; k ++){
               
				if(isintree[j]*isintree[k] == 0 && isintree[j]+isintree[k] == 1 ){
					 if(matrix[j][k]<min){
					 	min = matrix[j][k];
					 	temp1 = j;
					 	temp2 = k;
					 }
				}
			}
		}
		mst = mst + min;
		isintree[temp1] = 1;
		isintree[temp2] = 1;
	}
	return mst;
}
int main(){
	//输入 
	int vnum; // 点数 
	int ednum; //边数 
    while(scanf("%d",&vnum)!=eof){
    	 scanf("%d",&ednum);
        if(vnum == 0)break;
    	if( ednum == 0 ){
            printf("0\n");
            continue;
        }
        //矩阵初始化
        int matrix[maxvertex][maxvertex] ;
        for(int i = 0; i <= vnum; i++){
        	for(int j = 0; j <= vnum; j++){
        		matrix[i][j] = inf;
			}
		}
		//输入边 边权 且 同一条边只保留最小边权
		for(int i = 0; i < ednum; i++){
			int v1,v2;
			int tempweight;
			scanf("%d",&v1);
			scanf("%d",&v2);
			scanf("%d",&tempweight);
			if(tempweight < matrix[v1][v2]){
				matrix[v1][v2] = tempweight;
				matrix[v2][v1] = tempweight;
			}
		}
      
		
		//prim算法+输出
		 printf("%d\n",prim(matrix,vnum,ednum));
	}
}