介绍

最小生成树一共两种算法prim算法以及kruskal算法，这两种算法最大的区别在于，一个是对点进行维护，一个是对边权进行维护，感觉kruskal算法相对方便一些

Prim算法

Prim算法类似于最短路的算法，每次找出距离上个点的距离最小的点，然后维护一个记录最小距离的数组

基础代码模板

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4+5;
const int inf = 0x3f3f3f3f;
int n,m,mindis[maxn],ans;
bool vis[maxn];
struct edge{
    int v,w;
    edge(int vv,int ww):v(vv),w(ww){}
};
vector<edge>e[maxn];
void add_edge(int u,int v,int w){
    e[u].push_back(edge(v,w));
}
void prim(){
    memset(mindis,inf,sizeof(mindis));
    memset(vis,false,sizeof(vis));
    mindis[1] = 0;//默认从1开始算 
    for(int i = 1 ; i <= n ; i++){
        int minn = inf,u = -1;
        for(int j = 1 ; j <= n ; j++){
            if(!vis[j] && minn > mindis[j]){
                minn = mindis[j];
                u = j;
            }
        }
        if(u == -1) break;
        vis[u] = true;
        for(int j = 0 ; j < e[u].size() ; j++){
            int v = e[u][j].v,w = e[u][j].w;
            if(!vis[v] && w < mindis[v]){
                mindis[v] = w;
            }
        }
    }
}


int main(){
//    cin >> n >> m ;
//    for(int i = 0 ; i < m ; i++){
//        int u,v,w;
//        cin >> u >> v >> w;
//        add_edge(u,v,w); 
//    }
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1;  j <= n ; j++){
            int w;
            cin >> w;
            add_edge(i,j,w);
        }
    }
    prim();
    for(int i = 1 ; i <= n ; i++) ans += mindis[i];
    cout << ans << endl;
    return 0;
}

Kruskal算法

Kruskal算法是对边进行维护，根据边权从小到大排序，利用并查集将在一个连通块中的点的父节点找到，第一次连通的点，边权一定最小，这样遍历所有的点，最后得到的答案就是最小生成树

基础代码模板

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4+5;
int pre[maxn],ans,n;

struct edge{
    int u,v,w;
    edge(int uu,int vv,int ww):u(uu),v(vv),w(ww){}
    friend bool operator <(edge a,edge b){
        return a.w < b.w;
    }
};
vector<edge>e;

void add_edge(int u,int v,int w){
    e.push_back(edge(u,v,w));
}

int find(int x){
    return x == pre[x] ? x : pre[x] = find(pre[x]);
} 

int main(){
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++) pre[i] = i;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            int w;
            cin >> w;
            add_edge(i,j,w);
        }
    }
    sort(e.begin(),e.end());
    for(int i = 0 ; i < e.size() ;i++){
        int r1 = find(e[i].u),r2 = find(e[i].v);
        if(r1 != r2){
            pre[r1] = r2;
            ans += e[i].w;
        }
    }
    cout << ans << endl;
    return 0;
}

Kruskal的应用：

题目背景

“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 t 区，而自己在 s 区。

该市有 m 条大道连接 n 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线，使得经过道路的拥挤度最大值最小。

输入格式

第一行有四个用空格隔开的 n，m，s，t，其含义见【题目描述】。

接下来 m 行，每行三个整数 u,v,w，表示有一条大道连接区 u 和区 v，且拥挤度为w。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数，代表最大的拥挤度。

输入输出样例

输入 #1 

3 3 1 3
1 2 2
2 3 1
1 3 3

输出 #1 

2

样例输入输出 1 解释

小明的妈妈要从 111 号点去 333 号点，最优路线为 111->222->333

题解：

这题问的是拥挤度最大值的最小值，开始题目意思理解错了，以为是最短路，后来发现意思是，找到从s到t过程中经历的路中的最大值，然后让这个最大值最小。直接用克鲁斯卡尔跑一遍，如果第一次找到s和t连通就输出这个边的权值，因为克鲁斯卡尔是需要对边权从小到大排序的，那么一旦连通，就说明在这个连通块中，最后那个边的值是最大的，又因为前面排序过了，所以这个值必是最小的

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;
int pre[maxn];
int n,m,s,t,cnt;

struct node{
    int u,v,w;
}e[maxn];

bool cmp(node a,node b){
    return a.w < b.w;
}

int find(int x){
    return x == pre[x] ? x :pre[x] = find(pre[x]);
}


int main(){
    cin >> n >> m >> s >> t;
    for(int i = 1 ; i <= n ; i++) pre[i] = i;
    for(int i = 0 ; i < m ; i++){
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e,e+m,cmp);
    for(int i = 0 ; i < m ; i++){
        int r1 = find(e[i].u),r2 = find(e[i].v);
        if(r1 != r2) pre[r1] = r2;
        if(find(s) == find(t)){
            cout << e[i].w << endl;
            return 0;
        }
    }
    return 0;
}