8/5 kruksal

标签：std struct int edge kruksal 1005

最有不限文体

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int fa[N];
int n,m;
int a[1005][1005];

struct edge{
    int u,v,w;
}e[N*N];

bool cmp(edge x,edge y){
    return x.w<y.w;
}

void Init(int n){
    for(int i=1; i<=n; i++){
        fa[i]=i;
    }
} 

int Merge(int a,int b){
    int p=fa[a];
    int q=fa[b];
    if(p==q){
        return 0;
    }
    for(int i=1; i<=n; i++){
        if(fa[i]==q){
            fa[i]=p;
        }
    }
    return 1;
}

int kru(int kk){
    int ans=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1; i<=m; i++){
        if(Merge(e[i].u,e[i].v)){
            ans+=e[i].w;
            kk--;
            if(kk==1){
                return ans;
            }
        }
    }
    return 0;
}

int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>a[i][j];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            m++;
            e[m].u=i;
            e[m].v=j;
            e[m].w=a[i][j];    
        }
    }
    Init(n);
    cout<<kru(n)<<endl;
    return 0;
}

 

标签：std,struct,int,edge,kruksal,1005
From： https://www.cnblogs.com/dxy09tj/p/17607543.html