前言

删繁就简。。。就用最小生成树。。。

1.思想

这里使用的是Kruskal算法。

  • 首先，MST的用途是在一个有n个点的无向图里，选出(n-1)条变组成一个新的连通图，求最小边权值。
  • 用并查集来维护图的连通性；
  • 将所有边按边权值从小到大排序；
  • 如果一条边连接的两个点不在一个并查集里，用这条边连接这两个点。
  • 因为是按边权值升序排序的，所以可以保证每次选取的都是最小边权值的边。

    2.最小生成树模板题

    【题目链接】
    洛谷【3366】
    【题目描述】
    如题，给出一个无向图，求出最小生成树。（原题说如果不连通则输出orz，然而并没有输出orz的点。。。）
    【输入格式】
    第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）
    接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi
    【输出格式】
    输出包含一个数，即最小生成树的各边的长度之和。
    【输入样例】

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

【输出样例】

7

【程序】

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include<iostream>
#include<algorithm>
#define M 500500
using namespace std;
int n,m,ans;
struct E{
	int from,to,w;
}e[M];
int tope;
inline void ae(int x,int y,int z)
{
	tope++;e[tope].to=y;e[tope].from=x;e[tope].w=z;
}
int fa[M];
inline void reinit()
{
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;
	}
}
int find(int x)
{
	if(x!=fa[x])
		fa[x]=find(fa[x]);
	return fa[x];
}
int pd(int x,int y)
{
	if(find(x)==find(y)) return 1;
	return 0;
}
inline void un(int x,int y)
{
	fa[find(x)]=find(y);
}
int cmp(E x,E y)
{
	return x.w<y.w;
}
int main()
{
	scanf("%d%d",&n,&m);
	int ta,tb,tc;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&ta,&tb,&tc);
		ae(ta,tb,tc);
	}
	sort(e+1,e+tope+1,cmp);
	reinit();
	for(int i=1;i<=tope;++i)
	{
		if(pd(e[i].from,e[i].to)==0)
		{
			un(e[i].from,e[i].to);
			ans+=e[i].w;
		}
	}
	printf("%d",ans);
	return 0;
}