求助:本人代码为何厌氧
查看原帖
求助:本人代码为何厌氧
1052894
Pacyd5楼主2024/7/1 21:05

RT.本人代码不开O2就能AC,但开了O2就WA on #8,9,10

#include<bits/stdc++.h>
using namespace std;
const int N=5000,M=400010;
struct sd
{
	int fr,to,w;
}E[M];
int n,m,ans,s,f[N];
bool cmp(sd a,sd b)
{
	return a.w<b.w;
}
int find(int p)
{
	if (p==f[p])
		return p;
	return f[p]=find(f[p]);
}
void kruskal()
{
	for(int i=1;i<=m;i++)
	{
		int u=E[i].fr,v=E[i].to;
		u=find(u);
		v=find(v);
		if (u!=v)
		{
			f[u]=v;
			ans+=E[i].w;
			s++;
		}
		if (s+1==n)
			return;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		f[i]=i;
	for(int i=1;i<=m;i++)
		cin>>E[i].fr>>E[i].to>>E[i].w;
	sort(E+1,E+m+1,cmp);
	kruskal();
	if (s+1!=n)
		cout<<"orz"<<endl;
	else
		cout<<ans<<endl;
}
2024/7/1 21:05
加载中...