有没有大佬指点一下哪错了qwq
  • 板块灌水区
  • 楼主j_steady
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/12/18 10:42
  • 上次更新2023/10/28 14:14:11
查看原帖
有没有大佬指点一下哪错了qwq
559503
j_steady楼主2021/12/18 10:42
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<iostream>
#define MAXN 200005

using namespace std;

int n,m,fa[MAXN];
struct edge{
	int u,v,w; 
}e[MAXN];
bool cmp (edge a,edge b){
	return a.w < b.w; 
}
void init(int n){
	for (int i=1;i<=n;i++){
		fa[i]=i;
	}
}
int find (int x){
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
//void join (int x,int y){
//	int f1=find (x),f2=find(y);
//	if(f1==f2) return;
//	else fa[f1]=f2;
//}

int t=0;
void add(int u,int v,int w){
	e[++t].u=u;
	e[t].v=v;
	e[t].w=w;
	//fa[e[t].v]=e[t].u;
}
int cnt =0;
int sum=0;
int main (){
	scanf ("%d%d",&n,&m);
	init(n);
	for (int i=1;i<=m;i++){
		int a,b,c;
		scanf ("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	sort (e+1,e+m+1,cmp);
	for (int i=1;i<=m;i++){
		int aa=find(e[i].u),bb=find(e[i].v);
		if (aa==bb) continue;
		else fa[aa]=bb;
		sum+=e[i].w;
		if (++cnt==n-1) break;
		}
	
	int ans=0;
	for (int i=1;i<=m;i++){
		if (find(i)==i) ans++;
	}
	if (ans > 1) printf ("orz");
	else printf ("%d",sum);
	return 0;
}
2021/12/18 10:42
加载中...