文章

3

粉丝

181

获赞

1

访问

23.6k

头像
最小生成树kruskal模板题
P1312 浙江大学机试题
发布于2021年4月22日 17:33
阅读数 6.5k

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

const int MAXN = 102;

struct Edge{
    int a,b;
    int val;
    bool operator < (const Edge &A) const{
        return val<A.val;
    }
};
Edge edge[MAXN];

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

void init(int N){
    for(int i=1;i<=N;i++){
        father[i] = i;
    }
}


int main(){
    int N,M;
    while(cin>>N>>M){
        if(N==0)
            break;
        init(N);
        for(int i=0;i<N;i++){
            cin>>edge[i].a>>edge[i].b>>edge[i].val;
        }
        sort(edge,edge+N);
        int ans = 0;
        int cnt = 0;
        for(int i=0;i<N;i++){
            int a = edge[i].a;
            int b = edge[i].b;
            a = find(a);
            b = find(b);
            if(a!=b){
                ans+=edg...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发