Pacyd5 @ 2024-07-01 21:05:59
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;
}
by King_and_Grey @ 2024-07-01 21:08:10
@Pacyd5 P1928 外星密码这题一吸氧就 RE,不吸氧就AC
和你的情况差不多(但我也不知道为什么)
by ATZdhjeb @ 2024-07-01 21:09:10
by Pacyd5 @ 2024-07-01 21:13:33
@ATZdhjeb thk.此贴结