预备知识:并查集,参考我的博客 https://blog.csdn.net/hpu2022/article/details/81710828
这里再给出一种并查集的写法:
const int MAXN = (int) 1e6+7;
int pre[MAXN];
void init(int n)
{
for(int i=0; i<n; i++)
pre[i] = i;
}
int find(int x)
{
if(pre[x] == x)
return pre[x];
else
return pre[x] = find(pre[x]);
}
void join(int x, int y)
{
x = find(x);
y = find(y);
if(x != y)
pre[x] = y;
}
Kruskal算法按照边的权值的顺序从小到大查看一遍,如果不产生圈,重边,就把当前这条边加入到生成树当中。
解释:在解决实际问题的时候,我们把边用数组存起来,然后按照权从小到大排序。从权值最小的边开始,不断选取权值小的边。每当选取一条边就把这条边连接的两个顶点加入到并查集中。在随后选取边的过程中,如果当前将要选取的边的两个顶点都在并查集中,就说明是重边,不再选取这条边。当选取了n-1条边时,就说明已经把n个顶点都选取过了,最小生成树已经生成。可以不在判断随后的边。
code:
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1000 + 7;
const int INF = 0x3f3f3f3f;
struct node {
int a, b, c; // a->b 有一条权值为c的边
};
struct node road[MAXN << 2];
bool cmp(node r1, node r2)
{
return r1.c < r2.c;
}
int pre[MAXN];
void init()
{
for(int i=0; i<MAXN; i++)
pre[i] = i;
}
int find(int x)
{
if(x == pre[x])
return x;
return pre[x] = find(pre[x]);
}
void join(int x, int y)
{
x = find(x);
y = find(y);
if(x != y)
pre[x] = y;
}
int main()
{
int n, m; // n个顶点, m条边
scanf("%d%d", &n, &m);
for(int i=0; i<m; i++)
scanf("%d%d%d", &road[i].a, &road[i].b, &road[i].c);
sort(road, road+m, cmp);
init();
int cnt = 0;
int cost = 0;
for(int i=0; i<m; i++)
{
int fa = find(road[i].a);
int fb = find(road[i].b);
if(fa != fb)
{
pre[fa] = fb;
cost += road[i].c;
cnt ++;
if(cnt == n-1)
break;
}
}
printf("%d\n", cost);
return 0;
}