QBMST - Cây khung nhỏ nhất ( HEAP )
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
#define MAX 15151
using namespace std;
struct edge {
int u,v,w;
bool operator < (const edge &x) const {
if (w<x.w) return (true);
if (w>x.w) return (false);
return (u+v<x.u+x.v);
}
};
int up[MAX];
edge e[MAX];
int m,n;
void init(void) {
scanf("%d",&n);
scanf("%d",&m);
int i;
for (i=1;i<=m;i=i+1) {
scanf("%d",&e[i].u);
scanf("%d",&e[i].v);
scanf("%d",&e[i].w);
}
for (i=1;i<=n;i=i+1) up[i]=-1;
sort(&e[1],&e[m+1]);
}
int find(int x) {
if (up[x]<0) return (x);
up[x]=find(up[x]);
return (up[x]);
}
void join(int a,int b) {
int x=find(a);
int y=find(b);
if (x==y) return;
up[y]=x;
}
void kruskal(void) {
int i,c,s;
c=0;s=0;
for (i=1;i<=m;i=i+1) {
if (find(e[i].u)!=find(e[i].v)) {
join(e[i].u,e[i].v);
c=c+1;
s=s+e[i].w;
if (c==n-1) {
printf("%d",s);
return;
}
}
}
}
int main(void) {
init();
kruskal();
return 0;
}