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

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

#### 思路

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

##### 源码
``````//
//  253.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//

#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;
}

``````