我要当第一 • 4个月前
using namespace std; int n,m; long long sum=0,k=0; int fa[N];
struct node {
int u,v,w;
}e[N];
bool cmp(node &a,node &b) {
return a.w<b.w;
} int vis[N]; void init() {
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
}
int Find(int i) {
if(i==fa[i])
{
return i;
}
else{
fa[i]=Find(fa[i]);
return fa[i];
}
} void unionn(int i,int j) {
int ifa=Find(i);
int jfa=Find(j);
fa[jfa]=ifa;
} void kruskal() {
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(k==n-1)
{
break;
}
if(Find(e[i].u)!=Find(e[i].v))
{
unionn(e[i].u,e[i].v);
sum+=e[i].w;
vis[k]=1;
k++;
}
}
} int main() {
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>e[i].u>>e[i].v>>e[i].w;
}
init();
kruskal();
if(k!=n-1)
{
cout<<"orz";
return 0;
}
cout<<sum;
return 0;
}
评论:
请先登录,才能进行评论