RT

Kru算法模板,大红大紫,求查错

代码没有考虑orz的情况

//邻接表 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010; 
int as=0; 
struct e{
    int from;//边的起点 
    int to;//边的终点 
    int now;//权值 
}a[MAXN];
int qian[MAXN];
int from,to,now,ans,k;
bool cmp(e a,e b){//自定义cmp函数,权值小的优先 
    return a.now<b.now;
}
int get_f(int x){
    if(qian[x]==x){
        return x;   
    }
    qian[x] = get_f(qian[x]);
    return qian[x];
}
bool check(int x,int y){
    int r1=get_f(x),r2=get_f(y);
    if(r1!=r2){
        qian[r1]=r2;
        return 1;
    }
    return 0;
}
int main(){
    int n,m;
    scanf("%d&d",&n,&m);
    for(int i=1;i<=m;i++){
        qian[i]=i;//自我为夫 
        scanf("%d%d%d",&from,&to,&now);
        a[as].from=from;
        a[as].to=to;
		a[as].now=now;
        as++;
    }
    sort(a,a+as,cmp);//权值排序 
    for(int i=0;i<as-1;i++){
        if(check(a[i].from,a[i].to)){//在不同集合(不构成环) 
            ans+=a[i].now;//确认连接 
            k++;//连接边数++ 
            if(k==n-1){//连接完了所有的点     
                break;
            }
        }
    }
    printf("%d",ans);//最小代价 
    return 0;
}