隔了几个月，又开始写博客了qwq
kruskal
时间复杂度为O(nlogn)
它的算法思路是这样的：
我们根据边的权值将所有边排序，然后枚举每条边，用并查集去查询这条边的两个端点是否在同一集合内，若在同一集合内，则删掉这条边，若不在同一结合则加入这条边，并将这两个端点所在的集合合并。
附一下代码：
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
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,q[6000];
struct lalala{
int x,y,z,save;
}a[210000];
int mysort(lalala a,lalala b)
{
return a.z < b.z;
}
int work(int x,int y)
{
while(q[q[x]] != q[x]) q[x] = q[q[x]];
while(q[q[y]] != q[y]) q[y] = q[q[y]];
if(q[x] == q[y]) return 1;
else
{
q[q[y]] = q[x];
return 0;
}
}
int main()
{
long long ans = 0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) q[i]=i;
for(int i=1; i<=m; i++)
{
cin>>a[i].x>>a[i].y>>a[i].z;
ans += a[i].z;
}
sort(a+1,a+m+1,mysort);
for(int i=1;i<=m;i++)
{
if(!work(a[i].x,a[i].y)) ans -= a[i].z;
}
cout << ans;
return 0;
}
|
prim
时间复杂度O(n2)
跑得慢，代码长，没特殊功能，真不知道为什么要学它qwq……
prim的思想和某最短路算法的思路是类似的，我们将更新过的点标为白色，没有更新过的标为蓝色，然后枚举每一个蓝点（按minn值从小到大更新，这里貌似可以用堆优化，然而我比较懒qwq）并更新为白点，并用它去更新其他的蓝点（这里不用把被更新的点标为白色，不然它们就没法更新其他点，也没法被其他的点更新了）。最后将每个点的minn值加起来就好啦。
附一下代码：
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
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define INF 2147483647
using namespace std;
struct node{
int k,dis;
bool operator < ( const node &x )const{return x.dis < dis;}
};
priority_queue<node> que;
long long n,m,s,d[1000005],cnt,D[1000005],v[1000005];
struct Edge{
int to,next,x;
}edge[2000005];
void add(int x,int y,int a)
{
edge[++cnt].to = y;
edge[cnt].x = a;
edge[cnt].next = d[x];
d[x] = cnt;
}
int main()
{
int x,y,a;
scanf("%lld%lld%lld",&n,&m,&s);
for(register int i = 1; i <= m; i++)
{
scanf("%d%d%d",&x,&y,&a);
add(x,y,a);
}
que.push((node){s,0});
for(register int i = 1; i <= n; i++) D[i] = INF;
D[s] = 0;
while(!que.empty())
{
node u = que.top();
que.pop();
if(v[u.k]) continue;
v[u.k] = 1;
for(register int i = d[u.k]; i; i = edge[i].next)
{
if(D[edge[i].to] > D[u.k] + edge[i].x)
{
D[edge[i].to] = edge[i].x + D[u.k];
if(!v[edge[i].to]) que.push((node){edge[i].to,D[edge[i].to]});
}
}
}
for(register int i = 1; i <= n; i++) printf("%d ",D[i]);
printf("\n");
return 0;
}
|
prim的堆优化
既然prim和某最短路算法的思路是相似的，那么ta和某最短路算法一样也可以用堆优化，可以把时间复杂度从O(n2)降到O(nlongn)
依然是跑得慢，代码长，没特殊功能qwq……
附一下代码：
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
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define INF 0x7fffffff
#define re register
using namespace std;
int read()
{
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
struct edge{
int x,y,z;
}a[500005];
struct EDGE{
int next,to,x,save;
}e[500005];
struct node{
int k,dis;
bool operator < (const node & x) const {return x.dis < dis;}
}now;
priority_queue <node> que;
int cnt,d[100005];
void add(int x,int y,int a)
{
e[++cnt].to = y;
e[cnt].x = a;
e[cnt].next = d[x];
d[x] = cnt;
}
int n,m,q,x,y,z,ans,minn[100005],vis[100005];
int mysort(edge a1, edge a2)
{
if(a1.x != a2.x) return a1.x < a2.x;
if(a1.y != a2.y) return a1.y < a2.y;
return a1.z < a2.z;
}
int main()
{
n = read();
m = read();
for(re int i = 1; i <= m; i++)
{
a[i].x = read(); a[i].y = read(); a[i].z = read();
}
sort(a + 1, a + m + 1, mysort);
for(re int i = 1; i <= m; i++)
if(a[i].x != a[i - 1].x || a[i].y != a[i - 1].y)
{
add(a[i].x, a[i].y, a[i].z);
add(a[i].y, a[i].x, a[i].z);
}
for(re int i = 1; i <= n; i++) minn[i] = INF;
que.push((node){1,0});
while(!que.empty())
{
now = que.top();
que.pop();
vis[now.k] = 1;
for(re int i = d[now.k]; i; i = e[i].next)
if(!vis[e[i].to] && e[i].x < minn[e[i].to])
{
minn[e[i].to] = e[i].x;
que.push((node){e[i].to,minn[e[i].to]});
}
}
for(re int i = 2; i <= n; i++) ans = ans + minn[i];
printf("%d\n",ans);
return 0;
}
|
推荐例题：【模板】最小生成树
