2626: 贪心算法-最小生成树

#include <stdio.h>
#include <stdlib.h>

#define MAX 100
#define MAXCOST 0x7fffffff

int graph[MAX][MAX];

int Prim(int graph[][MAX],int n, int v){ // 从顶点v开始计算 
	int lowcost[MAX]; //lowcost[i]记录以顶点i为终点的边的最小权值	
	int closet[MAX]; // closet[i]记录权值为lowcost[i]的起点，本题如果要求输出最小生成树上的边的信息，则该数组不能省略。 
	int i,j,sum=0;
	for(j=0; j<n; j++){ //初始化lowcost和closet 
		
	}	
	lowcost[v]=0; //标记顶点v已加入到最小生成树中 
	for(i=2; i<=n; i++){ // 循环n-1次，每次找到一条当前权重最小的边 		
		int min=MAXCOST; // 记录lowcost中当前最小值，初始化为无穷
		int index;  // 记录lowcost中当前最小值的下标 
		for(j=0; j<n; j++){
			
		}
		sum=sum+min;  
		lowcost[index]=0;
		for(j=0; j<n; j++){ //更新lowcost和closet 
			
		}
	}
	return sum;
}

int main(void){
	int i,j,k,n,m; // m表示图中边的个数，n表示图中顶点的个数 
	int u,v,w;
	scanf("%d %d", &n,&m); 
	for(i=0; i<n; i++){ // 初始化图的存储结构邻接矩阵，0号单元存储有效数据 
		for(j=0; j<n; j++){
			graph[i][j]=MAXCOST;
		}
	}
	for(k=1; k<=m; k++){ //读取边信息构造邻接矩阵 
		scanf("%d %d %d", &u,&v,&w);
		graph[u][v]=w;
		graph[v][u]=w;
	}
	int mincost=Prim(graph,n,0); // 从顶点0开始求最小生成树
	printf("%d\n",mincost);
	return 0;	
}

4 4
0 1 10
0 3 40
1 2 20
2 3 30

60