最小生成树

最小生成树有两种算法

Prim & Kruskal

1. Prim

#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define maxn 5005
int cost[maxn][maxn],minn,n,m,v2[maxn],tot=1,now,ans;
bool v1[maxn];
inline void getcost()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cost[i][j]=inf;
        }
    }
    for(int i=1,u,v,w; i<=m; i++) {
           scanf("%d%d%d",&u,&v,&w);
                if(cost[u][v]>w) {
                    cost[u][v]=cost[v][u]=w;
                }
    }//初始化cost数组
    for(int i=1; i<=n; i++) {
        v2[i]=cost[1][i];
    }
    v1[1]=1;//找出与1节点相连的边并进行标记
}
inline int prim()
{
    while(tot<n) { //最小生成树的概念
        minn=inf;
        tot++;
        for(int i=1; i<=n; i++) {
            if(!v1[i]&&v2[i]<minn) {
                minn=v2[i];
                now=i;
            }
        }//找出最小边

        ans+=minn;//更新答案
        for(int i=1; i<=n; i++) {
            if(v2[i]>cost[now][i]&&!v1[i]) {
                v2[i]=cost[now][i];
            }
        }
        v1[now]=1;//在找出与now节点相连的边并进行标记
    }
    return ans;
}
int main()
{
    getcost();
    printf("%d",prim());
    return 0;//主函数不解释
}

2. Kruskal

#include<bits/stdc++.h>
#define max(a,b) return a>b?a:b 
using namespace std;
struct Edge{int pointA,pointB,w;}edge[200005];
int father[5005],n,m,ans,eu,ev,cnt;
inline bool cmp(Edge a,Edge b){return a.w<b.w;}//快排的依据
inline int findfather(int x){
    while(x!=father[x]) x=father[x]=father[father[x]];
    return x;
}//并查集模板，用while循环比递归版快
inline void kruskal(){
    sort(edge+1,edge+m+1,cmp);//将边的权值排序
    for(int i=1;i<=m;i++){
        eu=findfather(edge[i].pointA), ev=findfather(edge[i].pointB);
        if(eu==ev) continue;//若出现环，则continue
        ans+=edge[i].w;//更新答案
        father[ev]=eu; cnt++;
        if(cnt==n-1) break;//循环结束条件
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) father[i]=i;//初始化并查集
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&edge[i].pointA,&edge[i].pointB,&edge[i].w);
    kruskal();
    printf("%d",ans);
    return 0;
}