不知道哪里错了,样例一直输出orz。
#include<bits/stdc++.h>
using namespace std;
int n,m,father[5005],ans,sum;
struct Edge{
int u,v,d;
bool operator < (const Edge &b)const{
return d>b.d;
}
}edge[200010];
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void merge(int x,int y)
{
father[x]=y;
}
inline void init()
{
for(int i=1;i<=n;i++)
merge(i,i);
}
inline void input()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
edge[i].u=read(),edge[i].v=read(),edge[i].d=read();
}
inline int find(int x)
{
if(father[x]==x)
return x;
return father[x]=find(father[x]);
}
inline void kruskal()
{
sort(edge+1,edge+m+1);
for(int i=1;i<=m;i++)
{
int start=find(edge[i].u),end=find(edge[i].v);
if(start==end)
continue;
ans+=edge[i].d;
merge(start,end);
sum++;
if(sum==n-1)
{
cout<<ans;
return;
}
}
cout<<"orz";
}
int main()
{
init();
input();
kruskal();
return 0;
}