kruskal算法胡乱输出orz求助
查看原帖
kruskal算法胡乱输出orz求助
755447
kato__megumi楼主2023/3/12 11:10

代码37分,最后一个特判orz点能过。WA的点全是因为错误输出orz。 初步判断是被Xi==Yi的情况卡掉了,求神犇救命

#include<bits/stdc++.h>
using namespace std;
const int N=20005;
int n,m,u,v,father[N],ans,tag;
struct edge{
    int start,to;long long val;
}bian[2000005];
bool cmp(edge a,edge b){
    return a.val<b.val;
}
int find(int x){
	if(x==father[x])return x;
	return father[x]=find(father[x]);
}
void bing(int x,int y){
	x=find(x),y=find(y);
	father[x]=y;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)father[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&bian[i].start,&bian[i].to,&bian[i].val);
	}
	sort(bian+1,bian+m+1,cmp);//快排边长
	for(int i=1;i<=n;i++){//kruskal
		u=find(bian[i].start),v=find(bian[i].to);
		if(u==v)continue;
		father[u]=v;
		tag++;//边的数量 
		ans+=bian[i].val;
		if(tag==n-1)break;//树已成型 
	}
	for(int i=1;i<n;i++){
		//cout<<find(i)<<endl;//debug
		if(find(i)!=find(n)){
			printf("orz");
			return 0;
		}//判断是否连通
	}
	cout<<ans;
	return 0;
}
2023/3/12 11:10
加载中...