题目描述

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式

输入数据包括城镇数目正整数 N（≤1000）和候选道路数目 M（≤3N）；随后的 M 行对应 M 条道路，每行给出 3 个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从 1 到 N 编号。

输出格式

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出 −1，表示需要建设更多公路。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例

1
12

思路

链式前向星存图，然后从某一个结点开始遍历整个图，每次选择已经收入囊中的结点距离他们所能到达的结点的最小权值即可。

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int fw=1e5+10;
int e[fw],w[fw],ne[fw],h[fw],bj[fw],xb,n,m,zx,gs;//e数组存储终点值，w数组存储权值，ne数组存储下一个结点的下标，h数组存储头结点下标，bj数组标记是否被访问过，xb用来存储e数组用到了哪里，zx用来存储最小总权值，gs用来存储已经收入囊中的结点个数。
vector<int>v;//存储已经收入囊中的结点
void cr(int x,int y,int z){//链式前向星插入模板
	e[xb]=y;
	w[xb]=z;
	ne[xb]=h[x];
	h[x]=xb++;
}
void prim(int x){
	if(gs==n-1){//如果所有结点都被访问了就直接输出即可
		cout<<zx;
		exit(0);
	}
	bj[x]=1;
	v.push_back(x);//收入囊中
	int t=99999999,u=-1;
	for(auto k:v){//寻找最小权值的边
		for(int i=h[k];i!=-1;i=ne[i]){
			if(w[i]<t&&(!bj[e[i]])){
				t=w[i];
				u=e[i];
			}
		}
	}
	if(u!=-1){
		zx+=t;
		gs++;
		prim(u);
	}
}
int main(){
	memset(h,-1,sizeof(h));
	cin>>n>>m;
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		cr(a,b,c);
		cr(b,a,c);
	}
	prim(n);
	cout<<0;
	return 0;
}