定义

  • 对于一个带权图，寻找一个包含所有节点的树，使得树上节点的权值总和最小。

Prim算法

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
#include<bits/stdc++.h>
using namespace std;
#define pr pair<int,int>
const int N = 5e3+5;
int n,m;
vector<vector<pr>> g(N);
vector<array<int,3>> mst;
int ans;
int vis[N];

//Prim算法
int main () {
    cin>>n>>m;
	//输入无向图(邻接表)
    for(int i=0;i<m;i++)
    {
        int x,y,z;cin>>x>>y>>z;
        g[x].push_back({y,z});
        g[y].push_back({x,z}); //{终点，权重}
    }
    //采用优先队列，每次取得待选边得权重最小的一边,greater<>表示小数优先。
    priority_queue<array<int,3>,vector<array<int,3>>,greater<>> pq;
    //标记已经走过的节点
    vis[1] = 1;
    //将节点1的边加入优先队列
    for(auto& p:g[1]) 
    {
        pq.push({p.second,1,p.first}); //{权重，起点，终点}
    }
    //当最小生成树的大小=n-1时结束循环，当然要保持pq非空
    while(!pq.empty() && mst.size() < n-1)
    {
	    //取得待选边的最小边
        auto [weight,u,v] = pq.top();
	    //弹出待选队列
        pq.pop();
        //不再访问已经更新过的边
        if(vis[v]) continue;
        //更新标记为已经走过
        vis[v] = 1;
        //将边加入mst
        mst.push_back({weight,u,v});
        //更新最小权重
        ans+=weight;
        //将新边(另一个端点的未访问出边)加入待选队列
        for(auto p:g[v])
        {
            if(vis[p.first]) continue;
            pq.push({p.second,v,p.first}); ////{权重，起点，终点}
        }
    }
    cout<<ans<<"\n";
    return 0;
}

Kruskal算法

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
#include<bits/stdc++.h>
using namespace std;
#define pr pair<int,int>
const int N = 5e3+5;
int n,m;
vector<vector<pr>> g(N);
vector<array<int,3>> G;
vector<array<int,3>> mst;
vector<int> fa(N); // 并查集判断是否连通
int ans;
int vis[N];

//并查集中的找根
int findroot(int k)
{
    if(k == fa[k])
    {
        return k;
    }
    //路径压缩优化时间复杂度
    return fa[k] = findroot(fa[k]);
}

//连接两个点
void connect(int i,int j)
{
    int ri = findroot(i);
    int rj = findroot(j);
    if(ri == rj) return;
    //将一个节点的根与另一个节点的根连接起来形成父子关系
    fa[ri] = rj;
}

//判断是否连通
bool isconnected(int i,int j)
{
    int ri = findroot(i);
    int rj = findroot(j);
    return ri == rj;
}

//Kruskal算法
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=0;i<m;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        G.push_back({z,x,y}); //权重，起点，终点
        connect(x,y);
    }
    for(int i=2;i<=n;i++)
    {
        if(!isconnected(1,i))
        {
            cout<<"orz\n";
            return 0;
        }
    }
    for(int i=1;i<=n;i++) fa[i] = i;
    //按照权重升序排序
    sort(G.begin(),G.end());int index = 0;
    while(mst.size() < n-1 && index < G.size())
    {
	    //不断取出权重最小的边
        auto [weight,u,v] = G[index];index++;
        //如果已经连接了两个点则跳过
        if(isconnected(u,v)) continue;
        connect(u,v);
        mst.push_back({weight,u,v});
        ans+=weight;
    }
    cout<<ans<<"\n";
    return 0;
}