萌新刚学 OI 求调 Kruskal 板子(P3366)
  • 板块灌水区
  • 楼主OrientDragon
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/4 16:23
  • 上次更新2024/10/4 18:22:26
查看原帖
萌新刚学 OI 求调 Kruskal 板子(P3366)
1173109
OrientDragon楼主2024/10/4 16:23
#include <bits/stdc++.h>
#define int long long
int read(int x=0){
	char ch=getchar();
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57){
		x=x*10+(ch^48);
		ch=getchar();
	}
	return x;
}
void write(int x){
	if(x>9)write(x/10);
	putchar(x%10^48);
}
struct edge{
	int u,v,w;
	bool operator<(const edge&x)const{
		return w<x.w;
	}
}a[200005];
int fa[5005],n,m,cnt,ans,now=1;
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)a[i].u=read(),a[i].v=read(),a[i].w=read();
	std::sort(a+1,a+n+1);
	while(cnt<n-1&&now<=m){
		int tmp1=gf(a[now].u),tmp2=gf(a[now].v);
		if(tmp1!=tmp2)cnt++,ans+=a[now].w,fa[tmp1]=tmp2;
		now++;
	}
	if(cnt==n-1)write(ans);
	else puts("orz");
}

直角;自从加入判断是否 orz 以后好像就只输出 orz 了。。。帮调一下 玄关

2024/10/4 16:23
加载中...