kruskal三个TLE 求助!
查看原帖
kruskal三个TLE 求助!
398048
qq2499899011楼主2021/4/1 18:18

查并集也压缩路径了,不知道为啥还是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;
}
2021/4/1 18:18
加载中...