最小生成树（简单讲解，通俗易懂）

什么是树呢？

有三个特点：

无向图，连通，无环

其他性质：树中点的个数总是比边的个数多1，根节点没有父节点，树中节点的度数之和等于其边数。

树（tree）是一种特殊的图，一个图要成为树要满足三个条件：

该图是一个无向图（准确意义上来说，有根树的父子节点间的关系也可以算是有向边）

该图连通（即图上任意两点都可以互相到达）

该图无环（即图上任意两点间有且只有一条简单路径）

什么是生成树呢？

是一颗无根树，包含原图的所有节点，一个图可以有多颗生成树，可以理解为一个图删除多条边之后形成的树。

什么是最小生成树呢？

最小生成树（minimum spanning tree）其实就是一个生成树，不过它不同于一般的生成树，它的边权之和是最小的，即边权和最小的生成树，同一个图的最小生成树也可以有很多个，但是其边权和是一样的

下面放道例题：

道路建设https://ac.nowcoder.com/acm/problem/15108

输入描述:

测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000)，道路数目n(n<10000)，以及城市数目m(<100)。
接下来的n行给出建立公路的成本信息，每行给出三个整数，分别是相连的两个城市v1、v2(0<v1,v2<=m)以及建设公路所需的成本h(h<100)。

输出描述:

对每个测试用例，输出Yes或No。

示例1

输入

20 10 5
1 2 6
1 3 3
1 4 4
1 5 5
2 3 7
2 4 7
2 5 8
3 4 6
3 5 9
4 5 2

输出

Yes

示例2

输入

10 2 2
1 2 5
1 2 15

输出

Yes

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl "\n";
struct s{
	int v1,v2,h;
}z[10100];
int p[200];
bool cmp(s a,s b)
{
	return a.h<b.h;
}
int find(int x)
{
	return x==p[x]?x:find(p[x]);
}
void solve()
{
	int c,n,m,sum=0;
	while(cin>>c>>n>>m)
	{
	sum=0;
	for(int i=1;i<=101;i++)
	p[i]=i;
	for(int i=1;i<=n;i++)
	{
		cin>>z[i].v1>>z[i].v2>>z[i].h;
	}
	sort(z+1,z+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(find(z[i].v1)!=find(z[i].v2))
		{
			p[find(z[i].v2)]=find(z[i].v1);
			sum+=z[i].h;
		}
	}
	if(sum>c)
	{
	cout<<"No"<<endl;
	}
	else
	cout<<"Yes"<<endl;
	}
	return ;
}
signed main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	solve();
    return 0;
}