公路村村通

```
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<map>
#define  MAXV  1001
#define INF 32767//表示无穷大
using namespace std;

int lowcost[MAXV];
int edges[MAXV][MAXV];
int n, e;

void CreateMGraph();//建图 
void Prim();

int main()
{
	cin >> n >> e;
	if (e < n - 1)
		cout << -1 << endl;
	else
	{
		CreateMGraph();
		Prim();
	}
	return 0;
}
void CreateMGraph()//建图
{
	int i, j, a, b, c;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			edges[i][j] = INF;		
	for (i = 1; i <= e; i++)
	{
		cin >> a >> b >> c;
		edges[a][b] = c;
		edges[b][a] = c;
	}
}
void Prim()
{
	int i, min, j, mark=-1, sum = 0;
	for (i = 1; i <= n; i++)
		lowcost[i] = edges[1][i];
	lowcost[1] = 0;
	for (i = 1; i < n; i++)
	{
		min = INF;
		for (j = 1; j <= n; j++)
		{
			if (lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];/
				mark = j;
			}
		}
		sum = sum + min;
		lowcost[mark] = 0;
		for (j = 1; j <= n; j++)
			if (edges[mark][j] < lowcost[j])
				lowcost[j] = edges[mark][j];
	}
	for (j = 1; j <= n; j++)
		if (lowcost[j] != 0)
			break;
	if (j <= n)
	{
		cout << -1 << endl;
		return;
	}
	cout << sum<<endl;
}
```

顾风/中位数

内容风险标识

评论 (0)

顾风/中位数 .gitee-modal { width: 500px !important; }

内容风险标识