4.3算法之图论 253:丛林中的路

http://noi.openjudge.cn/ch0403/253

思路

kruskal,边集按照 cost 排序遍历,并查集检查连通性,如果边的两端不连通则加入集合,放进集合

源码
//
//  253.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

struct Edge{
    int st,ed,cost;
    Edge(int st,int ed,int cost):st(st),ed(ed),cost(cost){}
    bool operator < (const Edge & e) const{
        return cost<e.cost;
    }
};
using namespace std;
int find(vector<int>& father,int x){
    return father[x]==x?x:find(father,father[x]);
}
void un(int x,int y,vector<int> & father){
    int fx = find(father,x);
    int fy = find(father,y);
    if(fx>fy){
        father[fy]=fx;
    }else{
        father[fx]=fy;
    }
}
int main(){
    int num;
    while(cin>>num){
       // cout <<"num"<< num<<endl;
        if(num==0)break;
        vector<int> father(num);
        for(int i = 0;i < num;++i)father[i] = i;
        vector<Edge> edges;
        char stchar;
        num--;
        while(num--){
            cin >> stchar;
            int edgenum;
            cin >> edgenum;
            while(edgenum--){
                char edchar;
                int cost;
                cin >> edchar>>cost;
                edges.push_back(Edge(stchar-'A',edchar-'A',cost));
            }
        }
        sort(edges.begin(),edges.end());
        //kruskal
        int res = 0;
        for(int i = 0;i < edges.size();++i){
            //cout <<"cost"<< edges[i].cost<<endl;
            int st = edges[i].st;
            int ed = edges[i].ed;
            if(find(father,st)!=find(father,ed)){
                res+=edges[i].cost;
                un(st,ed,father);
            }
        }
        cout << res<<endl;

    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注