QBMST - Cây khung nhỏ nhất ( HEAP )
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
//#include <conio.h>
using namespace std;
#define MAX(a,b) ((a>b)?a:b)
#define CLEAR(A,N) (memset(A,0,(N)*sizeof(A[0])))
const int maxEdgeSize = 200005;
typedef struct{
int x,y,cost;
}graph;
graph v[maxEdgeSize];
int ar[maxEdgeSize];
int findSet(int i){
while(ar[i]!=i)
i = ar[i];
return i;
}
void makeUnion(int a,int p1,int b, int p2){
int x = MAX(p1,p2);
ar[a] = x;
ar[b] = x;
ar[p1] = x;
ar[p2] = x;
}
int adjustUsingUnionFind(int a,int b)
{
if(ar[a] == -1) ar[a] = a;
if(ar[b] == -1) ar[b] = b;
int p1 = findSet(a);
int p2 = findSet(b);
if(p1!=p2){
makeUnion(a,p1,b,p2);
return 1;
}
else return 0;
}
bool operator < (graph a, graph b)
{
return a.cost < b.cost;
}
int main()
{
//freopen("QBMST.in","r",stdin);
int m,n,i,minimumCost;
scanf("%d %d",&m,&n);
for(int i = 0;i<n;i++)
scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
sort(v,v+n);
for(int i = 0;i<=m;i++)
ar[i] = -1;
minimumCost = 0;
for(int i = 0;i<n;i++)
{
if(adjustUsingUnionFind(v[i].x,v[i].y)==1)
{
minimumCost+= v[i].cost;
//printf("%d\n",v[i].cost);
}
}
printf("%d",minimumCost);
//getch();
}