58分的大部分MLE的可能是数组开小了!
查看原帖
58分的大部分MLE的可能是数组开小了!
817442
Sakuya_maid楼主2023/3/15 10:19

我最开始看见题目样例是N<=5000,以为没有多大,一直58,后面把N改成2e5就过了,希望能帮到你

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
const int INF=0x3f3f3f3f;
int n,m;

// int g[4050][4050];
int p[N];
int res,cnt;

struct op
{
	int u,v,w;
}kru[N];

bool cmp(op a,op b)
{
	return a.w<b.w;
}

int find(int x)
{
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}

void kruskal()
{
	
	sort(kru+1,kru+1+m,cmp);
	
	for(int i=1;i<=m;i++)
	{
		int a=kru[i].u,b=kru[i].v,w=kru[i].w;
		
		a=find(a);
		b=find(b);
		
		if(a!=b)
		{
			p[a]=b;
			res+=w;
			cnt++;
		}
	}
	
	if(cnt<n-1) cout<<"orz"<<'\n';
	else cout<<res<<'\n';
}

signed main()
{
	cin >> n >> m;
	
	for(int i=1;i<=n;i++)
	p[i]=i;
	
	// memset(g,0x3f,sizeof g);
	for(int i=1;i<=m;i++)
	{
		int a,b,w;
		cin >> a >> b >> w;
		kru[i]={a,b,w};
	}
	
	kruskal();
	
	return 0;
}
2023/3/15 10:19
加载中...