200ms的板子，我尽力了，以我自己的能力没法再快了。。。
基于Kruskal的做法，跑了200ms，以我自己的能力没办法再快了，不过翻了几页评测列表发现我是最快的。。。我觉得应该会有更快的方法。
想法很简单，既然是最小生成树，把所有边按照边权升序排序，每次取一条最小权值的边，询问是否不在同一集合，如果不在，则最小生成树中就会有这条边，然后合并边所在的集合。生成树连接n个点，显然有n-1条边，所以开一个totedge来维护当前取到的边数，直到取完n-1条边为止。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 5005
#define maxm 200005
using namespace std;
struct Edge{
int from,to,dis;
bool operator <(const Edge &rhs)const{
return dis < rhs.dis;
}
};
Edge edge[maxm];
int father[maxm];
int n,m;
int totedge = ;
int k = ;
int ans = ;
inline int read(){
int num = ;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-')
flag = true;
else
num = c - '';
while (isdigit(c = getchar()))
num = num * + c - '';
return (flag ? - : ) * num;
}
void init(){
for (register int i=;i<=m;i++)
father[i] = i;
}
int find(int x){
if (father[x] == x)
return father[x];
father[x] = find(father[x]);
return father[x];
} void merge(int x,int y){
father[find(x)] = find(y);
} int main(){
n = read();m = read();
for (register int i=;i<=m;i++){
edge[i].from = read();
edge[i].to = read();
edge[i].dis = read();
}
sort(edge+,edge+m+);
init();
while (totedge < n-){
if (find(edge[++k].from) != find(edge[k].to)){
ans += edge[k].dis;
merge(edge[k].from,edge[k].to);
totedge++;
}
}
printf("%d\n",ans);
return ;
}