查并集也压缩路径了,不知道为啥还是TLE
#include<stdio.h>
typedef struct
{
int start,end,dis;
}Edge;
Edge edge[200005],temp;
int n,m,f[5005]={0},mindis=0,cnt=0,flag=0;
void scan()
{
scanf("%d %d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
edge[i].start=x;
edge[i].end=y;
edge[i].dis=z;
}
}
void initf()
{
for(int i=1;i<=n;i++)
{
f[i]=i;
}
}
void sort()
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m-i;j++)
{
if(edge[j].dis>edge[j+1].dis)
{
temp=edge[j];
edge[j]=edge[j+1];
edge[j+1]=temp;
}
}
}
}
void creat()
{
scan();
initf();
sort();
}
int find(int x)
{
if(x==f[x]) return x;
else return f[x]=find(f[x]);
}
int circle(Edge ed)
{
if(find(ed.start)==find(ed.end))
{
return 1;
}
return 0;
}
int main()
{
creat();
//OK
for(int i=1;i<=m;i++)//遍历每一条边
{
if(!circle(edge[i]))
{
f[find(edge[i].end)]=find(edge[i].start);
mindis=mindis+edge[i].dis;
cnt++;
}
if(cnt==n-1)
{
flag=1;
break;
}
}
if(flag) printf("%d\n",mindis);
else printf("orz\n");
return 0;
}