地址：http://ybt.ssoier.cn:8088/problem_show.php?pid=1348
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 int n,m,num;
5 struct edge{
6 int a,b,c;
7 }mp[90005];//边存放
8
9 struct CUNFANG{//记录数据
10 int x;
11 int y;
12 };
13
14 bool cmp(edge a,edge b){
15 return a.c<b.c;
16 }
17
18 vector<CUNFANG>cunfang;
19
20 int father[305];
21 int findfather(int x){//并查集
22 if(father[x]!=x) father[x]=findfather(father[x]);
23 else return father[x];
24 }
25
26 void kruskal(){//核心代码
27 num=0;
28 for(int i=1;i<=n;i++){
29 father[i]=i;
30 }
31 sort(mp+1,mp+m+1,cmp);
32 for(int i=1;i<=m;i++){
33 if(findfather(mp[i].a)!=findfather(mp[i].b)){
34 father[findfather(mp[i].a)]=findfather(mp[i].b);
35 num++;
36 CUNFANG temp;
37 temp.x=mp[i].a;temp.y=mp[i].b;
38 cunfang.push_back(temp);
39 if(num==n-1) break;
40 }
41 }
42 }
43
44 int main(){
45 cin>>n>>m;
46 for(int i=1;i<=m;i++){
47 int u,v,w;
48 cin>>u>>v>>w;
49 mp[i].a=u;
50 mp[i].b=v;
51 mp[i].c=w;
52 }
53 kruskal();
54 for(int i=0;i<n-1;i++){
55 cout<<cunfang[i].x<<" "<<cunfang[i].y<<endl;
56 }
57 return 0;
58 }