求助!
  • 板块学术版
  • 楼主poor_OIer
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/9/3 21:30
  • 上次更新2023/11/2 22:48:18
查看原帖
求助!
704634
poor_OIer楼主2023/9/3 21:30

不知道哪里错了,样例一直输出orz。

#include<bits/stdc++.h>
using namespace std;
int n,m,father[5005],ans,sum;
struct Edge{
	int u,v,d;
	bool operator < (const Edge &b)const{
		return d>b.d;
	}
}edge[200010];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void merge(int x,int y)
{
	father[x]=y;
}
inline void init()
{
	for(int i=1;i<=n;i++)
		merge(i,i);
}
inline void input()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
		edge[i].u=read(),edge[i].v=read(),edge[i].d=read();
}
inline int find(int x)
{
	if(father[x]==x)
		return x;
	return father[x]=find(father[x]);
}
inline void kruskal()
{
	sort(edge+1,edge+m+1);
	for(int i=1;i<=m;i++)
	{
		int start=find(edge[i].u),end=find(edge[i].v);
		if(start==end)
			continue;
		ans+=edge[i].d;
		merge(start,end);
		sum++;
		if(sum==n-1)
		{
			cout<<ans;
			return;
		}
	}
	cout<<"orz";
}
int main()
{
	init();
	input();
	kruskal();
	return 0;
}

题目穿越

2023/9/3 21:30
加载中...