社区讨论

C++只过了最后一个点,蒟蒻求调

P3366【模板】最小生成树参与者 4已保存回复 14

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@lo29ar16
此快照首次捕获于
2023/10/23 10:06
2 年前
此快照最后确认于
2023/11/03 10:18
2 年前
查看原帖
CPP
//P3366 【模板】最小生成树

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn=2e5+5;

int n,m;

struct EDGE//dui
{
	int left,right;
	int value;
};

EDGE edge[maxn];
int father[maxn];
int succeed=0,ans=0;

 int read()//right
{
	int f=1,x=0;
	char c;
	c=getchar();
	if(c=='-')f=-1,c=getchar();
	while('0'<=c&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

 bool cmp(EDGE x,EDGE y) //right
{
	return x.value<y.value;
}

 int find(int it)//right
{
	if(it==father[it])return it;
	else return father[it]=find(father[it]);
}

int main()
{
	n=read(),m=read();
	for(int i = 1;i<=n;i++)father[i]=i;
	for(int i = 1;i<=m;i++)
	{
		edge[i].left=read();
		edge[i].right=read();
		edge[i].value=read();
	}
	sort(edge+1,edge+1+m,cmp);
	for(int i = 1;i<=m;i++)
	{
		int findl=find(edge[i].left),findr=find(edge[i].right);
		if(findl!=findr)
		{
		father[findr]=findl;
		succeed++;ans+=edge[i].value;
		}
		if(succeed>=n-1)
		{
			cout<<ans<<endl;
			return 0;
		}
	}
	printf("orz\n");
	return 0;
}

回复

14 条回复,欢迎继续交流。

正在加载回复...