NKRACING - Vòng đua F1
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
#define MAX 100100
using namespace std;
struct edge {
int u,v,c;
edge(){}
edge(const int &_u,const int &_v,const int &_c) {
u=_u;v=_v;c=_c;
}
bool operator < (const edge &x) const {
if (c>x.c) return (true);
if (c<x.c) return (false);
return (u+v<x.u+x.v);
}
};
int m,n;
edge lst[MAX];
int up[MAX];
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 loadgraph(void) {
scanf("%d",&n);
scanf("%d",&m);
int i,u,v,c;
for (i=1;i<=n;i=i+1) up[i]=-1;
for (i=1;i<=m;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&c);
lst[i]=edge(u,v,c);
}
sort(&lst[1],&lst[m+1]);
}
void kruskal(void) {
int i;
int res=0;
for (i=1;i<=m;i=i+1) {
if (find(lst[i].u)!=find(lst[i].v)) join(lst[i].u,lst[i].v);
else res+=lst[i].c;
}
printf("%d",res);
}
int main(void) {
loadgraph();
kruskal();
return 0;
}