ljx979 @ 2024-10-17 12:06:08
include<bits/stdc++.h>
using namespace std;
int a[200005];
int ans=0;
int find(int a[],int i)
{
while(i!=a[i])
i=a[i];
return i;
}
void ad(int a[],int x,int y)
{
int r1=find(a,x);
int r2=find(a,y);
a[r2]=r1;
return;
}
bool check(int a[],int x,int y)
{
int r1=find(a,x);
int r2=find(a,y);
if(r1!=r2)
return true;
return false;
}
struct node
{
int x,y,dis;
}e[100005];
bool cmp(const node a,const node b)
{
return a.dis<b.dis;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<=n;i++) a[i]=i;
for(int i=0;i<m;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
e[i].x=x;
e[i].y=y;
e[i].dis=z;
}
sort(e,e+m,cmp);
for(int i=0;i<m;i++)
{
int x=e[i].x;
int y=e[i].y;
if(check(a,x,y))
{
// cout<<x<<' '<<y<<' '<<e[i].dis<<endl;
ans+=e[i].dis;
ad(a,x,y);
}
}
cout<<ans;
return 0;
}
by cly312 @ 2024-10-17 12:11:51
这是克鲁斯卡尔还是prim
by Zq_water @ 2024-10-17 12:13:33
@ljx979 您并查集的路径压缩呢
by Gcc_Gdb_7_8_1 @ 2024-10-17 12:19:14
@ljx979 跟 a
数组木有什么关系,主要如同上面的大佬所说,你 Kruskal 超时了。
by crz_qwq @ 2024-10-17 12:27:54
@ljx979 明显,你没有路径压缩