chenhao_li @ 2024-12-15 14:57:21
全部MLE,求解
#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans;//k is mst edges,ans
struct edge{
int u,v,w;
};
edge e[200010];
int fa[5010];
bool cmp(edge a,edge b){
return a.w>b.w;
}
int Find(int x){
if(fa[x]==x) return x;
else return fa[x]=Find(x);
}
void Union(int x,int y){
int fx=Find(x);
int fy=Find(y);
if(fx!=fy) fa[fy]=fx;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=1;//每个顶点自成联通分量
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+1+m,cmp);
//kruskal算法
for(int i=1;i<=m;i++){
if(Find(e[i].u)!=Find(e[i].v)){//边的两端不是一个联通分量
k++;
ans+=e[i].w;
Union(e[i].u,e[i].v);
if(k==n-1) break;
}
}
if(k!=n-1) cout<<"orz"<<endl;
else cout<<ans<<endl;
return 0;
}
by __yun__ @ 2024-12-15 14:59:41
@chenhao_li
for(int i=1;i<=n;i++) fa[i]=1;//每个顶点自成联通分量
改成
for(int i=1;i<=n;i++)fa[i]=i;
by __yun__ @ 2024-12-15 15:01:21
bool cmp(edge a,edge b){
return a.w>b.w;
}
改成
bool cmp(edge a,edge b){
return a.w<b.w;
}
by __yun__ @ 2024-12-15 15:05:17
else return fa[x]=Find(x);
改成
else return fa[x]=Find(fa[x]);
by chenhao_li @ 2024-12-15 15:33:15
@yun 谢谢高人指点