7-16 MST(Kruskal's OR Prim's algorithm) (14 分)
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected undirected weighted graph.
Input Specifcation:
There are two numbers(n, m) in first line, n means how many points are there, and m means how many edges are there(n<1000, m<2000), there are m lines following the first line, there are three numbers(x ,y and c) in each line, x and y mean the points in one edge, and c is the weights of the edge.
Output Specifcation:
The total weights of the minimum spanning tree.
Input Example:
5 5 1 2 1 2 3 1 3 4 2 4 5 1 5 1 1
Output Example::
4
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<bits/stdc++.h>
using namespace std;
int fa[1000],sum=0,t=0;
struct node{
int x,y,z;
}s[2000];
bool cmp(node i,node j){
if(i.z<j.z)
return 1;
else
return 0;
}
int myfind(int a){
int father;
if(fa[a]==a)
father=a;
else
father=myfind(fa[a]);
fa[a]=father;
return father;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z);
for(int i=1;i<=n;i++)
fa[i]=i;
sort(s+1,s+m+1,cmp);
for(int i=1;i<=m;i++){
int fathera=myfind(s[i].x);
int fatherb=myfind(s[i].y);
if(fathera!=fatherb){
fa[fathera]=fatherb;
t++;
sum+=s[i].z;
}
if(t==n-1)
break;
}
printf("%d",sum);
return 0;
}