最后一个点WA
查看原帖
最后一个点WA
466312
无奈之白楼主2022/6/18 23:31
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6;
int n,m,tot;
struct edge {
	int u,v,w,next;
} e[MAX];
int cmp(edge x,edge y){
	return x.w<y.w;
}
int head[MAX],f[MAX];
void add_edge(int u,int v,int w){
	e[++tot].u=u,e[tot].v=v,e[tot].w=w;
	e[tot].next=head[u],head[u]=tot;
}
int findf(int x){
	return x==f[x]?x:f[x]=findf(f[x]);
}
bool merge(int x,int y){
	int fx=findf(x),fy=findf(y);
	if(fx!=fy){
		f[fx]=fy;
		return 1;
 }
 	else return 0;
}
int main() {
	cin>>n>>m;
	int x,y,z;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		add_edge(x,y,z),add_edge(y,x,z);
 }
 	sort(e+1,e+1+tot,cmp);
 	int cnt=0,ans=0;
 	for(int i=1;i<=n;i++) f[i]=i;
 	for(int i=1;i<=tot;i++){
  		x=e[i].u,y=e[i].v;
  		if(merge(x,y)){
   		cnt++,ans+=e[i].w;
   		if(cnt==n-1) break;
   		 
  }
 }	if(ans)cout<<ans;
 	else cout<<"orz";
	return 0;
}
2022/6/18 23:31
加载中...