最小生成树

Prim

将任意节点作为根，找出与之相邻的所有边，将新节点作为根然后深搜，然后维护一个数组，$dis$，用作已用点到未用点的最短距离

证明：Prim算法之所以是正确的，主要基于一个判断：对于任意一个顶点v，连接到该顶点的所有边中的一条最短边(v, vj)必然属于最小生成树（即任意一个属于最小生成树的连通子图，从外部连接到该连通子图的所有边中的一条最短边必然属于最小生成树）

流程如下

代码为堆优化的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
55
56
57
58
59
60
61
62
63


#include<bits/stdc++.h>
#define FOR(i,l,r) for(register int i=l;i<=r;++i)
#define Graph(i,u) for(register int i=head[u];i;i=e[i].next)
using namespace std;
#define pii pair<int,int>
#define int long long
const int N=5e3+5,M=2e5+5;
const int inf=2147483647;
struct Edge{
    int u,v,w,next;
}e[M<<1];
int tot,head[M];
int n,m;
inline void addEdge(int u,int v,int w){
	e[++tot].u=u;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].next=head[u];
	head[u]=tot;
}
bool vis[N];
int dis[N];
int ans,now=1,cnt;
priority_queue<pii,vector<pii>,greater<pii>>q;
inline void Prim(){
    memset(dis,127,sizeof(dis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()&&cnt<n){
        // cout<<"QwQ";
        int d = q.top().first,u = q.top().second;
        q.pop();
        if(vis[u])continue;
        cnt++;
        ans+=d;
        vis[u]=1;
        Graph(i,u){
            if(e[i].w<dis[e[i].v]){
                dis[e[i].v]=e[i].w;
                q.push(make_pair(dis[e[i].v],e[i].v));
            }
        }
    }
    return;
}

signed main(){
    cin>>n>>m;
    FOR(i,1,m){
        int x,y,z;
        cin>>x>>y>>z;
        addEdge(x,y,z);
        addEdge(y,x,z);
    }
    Prim();
    if(cnt==n){
        cout<<ans<<endl;
    }
    else{
        cout<<"orz"<<endl;
    }
    return 0;
}

Kruskal

排序边权，优先选取权值较小的边，依次连接，若出现环就跳过（用并查集判断是否存在环），直到$已经使用的边数=总点数-1$即可

证明：如果某个连通图属于最小生成树，那么所有从外部连接到该连通图的边中的一条最短的边必然属于最小生成树。所以不难发现，当最小生成树被拆分成彼此独立的若干个连通分量的时候，所有能够连接任意两个连通分量的边中的一条最短边必然属于最小生成树

luogu

代码

 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


#include<bits/stdc++.h>
#define FOR(i,l,r) for(register int i=l;i<=r;++i)
#define Graph(i,u) for(register int i=head[u];i;i=e[i].next)
using namespace std;
#define int long long
const int N=5e3+5,M=2e5+5;
const int inf=2147483647;
struct Edge{
    int u,v,w,next;
    bool operator < (const Edge &b) const{
        return w<b.w;
    }
}e[M<<1];
int tot,head[M];
int n,m;
inline void addEdge(int u,int v,int w){
	e[++tot].u=u;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].next=head[u];
	head[u]=tot;
}
bool vis[N];
int dis[N];
int ans,now=1,cnt,fa[N];
inline int find(int x){
    while(x!=fa[x]){
        x=fa[x]=fa[fa[x]];
    }
    return x;
}
void Kruskal(){
    sort(e+1,e+m+1);
    FOR(i,1,m){
        int x = find(e[i].u),y = find(e[i].v);
        if(x==y){
            continue;
        }
        ans+=e[i].w;
        fa[y]=x;
        if(++cnt==n-1){
            break;
        }
    }
}
signed main(){
    cin>>n>>m;
    FOR(i,1,n){
        fa[i]=i;
    }
    FOR(i,1,m){
        int x,y,z;
        cin>>x>>y>>z;
        addEdge(x,y,z);
    }
    Kruskal();
    if(++cnt==n){
        cout<<ans<<endl;
    }
    else{
        cout<<"orz"<<endl;
    }
    return 0;
}