114514年没打版子全RE求助
查看原帖
114514年没打版子全RE求助
777131
IDNo1楼主2023/10/16 21:24
#include<bits/stdc++.h>
#define re register int
const int N=5e4+5;
using namespace std;
int n,m,a,b,c;
inline int read()
{
	re x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
struct Chtholly_tree//??? 
{
	int u,v,w;	
};
vector<Chtholly_tree> e;
int f[N];
bool cmp(Chtholly_tree a,Chtholly_tree b)
{
	return a.w<=b.w;
}
int u,v,w,ans,cnt;
int find(re k)
{
	if(k==f[k])return k;
	else f[k]=find(f[k]);
}
int fx,fy;
int _union(re x,re y)
{
	fx=find(x);
	fy=find(y);
	if(fx!=fy)
	{
		f[x]=fy;
	}
}
int main()
{
	n=read(),m=read();
	while(m--)
	{
		a=read(),b=read(),c=read();
		e.push_back({a,b,c});
	}
	for(re i=1;i<=n;i++)
	{
		f[i]=i;
	}
	sort(e.begin(),e.end(),cmp);
// 	for(re i=0;i<e.size();i++)
// 	{
// 		cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].w<<"\n"; 
// 	}
	for(re i=0;i<e.size();i++)
	{
		u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)!=find(v))
		{
			_union(u,v);
			ans+=w;
			cnt++;
		}
		if(cnt==n-1)
		{
			break;
		}
// 		cout<<ans<<" "<<cnt<<endl;
	}
	if(cnt==n-1)
	{
		cout<<ans;
	}
	else
	{
		cout<<"orz";
	}
	return 0;
}

yzm:xzrp祭

2023/10/16 21:24
加载中...