jhrsya

用户名：1564244868

访问量：13193

签　名：

等　　级
排　　名	642
经　　验	4065
参赛次数	2
文章发表	49
年　　龄	0
在职情况	学生
学　　校	南昌大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-最长公共子序列-题解(C++代码)
浏览：372

信息学奥赛一本通T1268-完全背包问题-题解(C++代码)
浏览：371

信息学奥赛一本通T1267-01背包问题-题解(C++代码)
浏览：373

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

数据结构-最小生成树（C++代码）

　　作者: jhrsya　　　　发表时间：2020-01-18 16:51:27 浏览：453　|　评论：0　

原题链接：数据结构-最小生成树

# PRIM算法与dijkstra算法极其相似，见https://blog.dotcpp.com/a/65305

#include <vector>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    #define INF (1 << 21) 
    
    static const int MAX = 500;
    int cost[MAX][MAX];  //cost[i][j]数组表示点i 与点j 的距离 
    int d[MAX];			//d[i]表示源点s 距离i 点的距离 
    bool used[MAX];		//used[i] 表示点i 是否加入已确定的顶点 
    int V;
    
    int prim(){
    
    	for(int i = 0; i < V; i++){		// 初始化d[i],和used[i]数组 
    		d[i] = INF;
    		used[i] = false;
    	}
    	d[0] = 0;		 
    	
    	int res = 0;		//总权值 
    	while(true){
    		int v = -1;
    		for(int u = 0; u < V; u++){		//从尚未使用过的顶点中选取距离最小的顶点 
    			if(!used[u] && (v == -1 || d[u] < d[v] )) v = u;
    		}
    		
    		if(v == -1) break;
    		used[v] = true;
    		
    		res += d[v]; 
    		for(int u = 0 ; u < V; u++){		//更新d[i]，取之前的的d[i]值与 v点到u 点距离的最小值 
    			d[u] = min(d[u], cost[v][u]);
    		}
    	}
    	return res;
    }
    int main()
    {
    	int s;
    	cin >> V;
    	int x;
    	for(int i = 0; i < V; i++){
    		for(int j = 0; j < V; j++){		//输入cost[][],如果输入的是0，则设置为无穷大，即两点间无边 
    			cin >> x;
    			if(x == 0)
    				cost[i][j] = INF;
    			else{
    				cost[i][j] = x;
    			}
    			 
    		}
    	}
    	
    	cout << prim() << endl;
    	
    	return 0;
    }

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

jhrsya

TA的其他文章

你可能喜欢

交换Easy （C++代码）

去掉双斜杠注释（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C二级辅导-进制转换（C语言代码）

数据结构-最小生成树（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

川哥的吩咐（C++代码）

分糖果（C++代码）

不会做的

WU-陶陶摘苹果2 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

矩形面积交（C语言代码）

简单的a+b （C语言代码）

jhrsya

TA的其他文章

你可能喜欢

交换Easy （C++代码）

去掉双斜杠注释 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C二级辅导-进制转换 （C语言代码）

数据结构-最小生成树 （C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

川哥的吩咐 （C++代码）

分糖果 （C++代码）

不会做的

WU-陶陶摘苹果2 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

矩形面积交 （C语言代码）

简单的a+b （C语言代码）

去掉双斜杠注释（C语言代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-进制转换（C语言代码）

数据结构-最小生成树（C++代码）

　　评论区

川哥的吩咐（C++代码）

分糖果（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

矩形面积交（C语言代码）