最小生成树

定义

• 边权和最小的生成树

Kruskal 算法

• 让边从小到大排序，如果不在同一集合，就加入

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 10,MAXM = 2e5 + 10;
int n,m;
int a[MAXN];
int find(int x)
{
	if(a[x] == x) return x;
	else return a[x] = find(a[x]);
}
struct edge{
	int u,v,val;
}ed[MAXM];
bool cmp(edge a,edge b)
{
	return a.val < b.val;
}
int sum;
void pre()
{
	for(int i = 1;i <= n;i++)
	a[i] = i;
}
void Kruskal()
{
	pre();
	sum = 0;
	for(int i = 1;i <= m;i++)
	{
		if(find(ed[i].u) != find(ed[i].v))
		{
			sum += ed[i].val;
			a[find(ed[i].u)] = find(ed[i].v);
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		cin >> ed[i].u >> ed[i].v >> ed[i].val;
	}
	sort(ed + 1,ed + 1 + m,cmp);
	Kruskal();
	bool flag = true;
	for(int i = 2;i <= n;i++)
	if(find(i) != find(i - 1))
	flag = false;
	if(flag)
	cout << sum;
	else
	cout << "orz";
}

Prim算法

• 搜索，对查到的边排序，取最小的边，加入

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 10,MAXM = 2e5 + 10;
int n,m;
struct edge{
	int v,val;
	edge* nex;
}ed[MAXM*2];
edge* head[MAXN];
int ptop = 0;
void add_edge(int u,int v,int val)
{
	ed[ptop].v = v,ed[ptop].val = val;
	ed[ptop].nex = head[u];
	head[u] = &ed[ptop];
	ptop++;
}
int sum = 0;
struct cmp{
	bool operator()(const pair<int,int>& a,const pair<int,int>& b)const{
		return a.second > b.second;
	}
};
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
bool use[MAXN];
int num = 0;
void Prim()
{
	pq.push({1,0});//距离点1距离为0
	while(!pq.empty() && num < n)
	{
		int x = pq.top().first,val = pq.top().second;
		pq.pop();
		if(use[x]) continue;
		use[x] = 1;//标记
		num++;
		sum += val;
		edge* p = head[x];
		while(p != NULL)
		{
			int y = p -> v,val = p -> val;
			pq.push({y,val});
			p = p -> nex;
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		int x,y,val;cin >> x >> y >> val;
		add_edge(x,y,val);
		add_edge(y,x,val);
	}
	Prim();
	if(num != n)
	cout << "orz";
	else
	cout << sum;
}