Kruskal最小生成树

继续写水题

最小生成树……

给定一张连通图,求图的最小生成树。

洛谷P3366 【模板】最小生成树

Kruskal算法

运用贪心思想,优先取较小的边来构树。

把边按从小到大排序,从最小的边开始选起。

对于此时的每条边,假如边上的两点不在同一连通分量里面,那么这条边为最小生成树上面的边,合并边上两个点到同一个连通分量;假如边上两点已经在同一连通分量了,那么证明之前已经有更小的边使得两点合并到同一连通分量里面,这条边就不在最小生成树上面了。

逐边迭代,统计最小生成树的边,假如“边数==点树-1”,那么就找到了某一个最小生成树。

判断是否在同一个连通分量,我们可以用并查集来维护。

路径压缩并查集复杂度是常数级别,std::sort的复杂度是$O(m\log m)$,扫一遍边是$O(m)$,所以总复杂度是$O(m\log m)$的。跑起来还是非常快的qwq

给出代码(注意是c++11)

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<vector>

using LL=long long;

const int inf=0x7fffffff;

class SpanningTree
{
private:
int n;
struct EDGE
{
int u,v,val;
bool operator <(const EDGE &tmp)const
{
return val<tmp.val;
}
};
std::vector<EDGE> E;
int *father;

int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}

LL Kruskal()
{
std::sort(E.begin(),E.end());
for(int i=1;i<=n;i++)
father[i]=i;

int cnt=0;
LL ans=0;
for(auto it : E)
{
int p=find(it.u),q=find(it.v);
if(p!=q)
{
father[p]=find(father[q]);
cnt++;
ans+=it.val;
}
if(cnt==n-1)
return ans;
}
return -1;
}

public:
SpanningTree(int n):n(n)
{
father=new int[n+10];
}

~SpanningTree()
{
E.clear();
delete [] father;
}

void input_edge(int m)
{
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
E.push_back((EDGE){u,v,w});
}
}

void Solve()
{
LL ans=Kruskal();
if(~ans)
printf("%lld\n",ans);
else
puts("orz");
}
};

int main()
{
int n,m;
scanf("%d%d",&n,&m);
SpanningTree *ST=new SpanningTree(n);
ST->input_edge(m);
ST->Solve();
delete ST;
return 0;
}