首页 > 代码库 > Kruskal算法 克鲁斯卡尔

Kruskal算法 克鲁斯卡尔

30行

#include <iostream>#include <algorithm>using namespace std;int f[5001],n,m,ans=0,i,ok;int getf(int x)//递归找爹 {    return f[x]==x?x:f[x]=getf(f[x]);}struct edge{    int u,v,w;    bool operator<(const edge sb)const    {        return this->w<sb.w;    }}a[200001];int main(){    cin >> n >> m;    for(i=1;i<=n;i++)        f[i]=i;    for(i=1;i<=m;i++)        cin >> a[i].u >> a[i].v >> a[i].w;    sort(a+1,a+1+m);    for(i=1,ok=1;ok<=n-1&&i<=m;i++)        if(getf(a[i].u)!=getf(a[i].v))            ans+=a[i].w,f[getf(a[i].u)]=getf(a[i].v),ok++;    cout << ans << endl;    return 0;}

  233

Kruskal算法 克鲁斯卡尔