这俩写法有啥区别?
  • 板块学术版
  • 楼主over_caykl
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/10/27 21:26
  • 上次更新2023/10/27 05:32:04
查看原帖
这俩写法有啥区别?
271803
over_caykl楼主2022/10/27 21:26

1:

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
struct qwq{
	int x,y,z;
	bool operator<(const qwq &a)const{
		return z<a.z;
	}
}e[N];
/*bool operator<(const qwq &a,const qwq &b){
	return a.z<b.z;
}*/

int ans,sum,f[N];
int n,m;
int getf(int a){
	if(f[a]==a) return a;
	return f[a]=getf(f[a]);
}
void Kruskal(){
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++){
		int fa=getf(e[i].x),fb=getf(e[i].y);
		if(fa!=fb){
			f[fa]=fb;
			ans+=e[i].z;
			sum++;
		}
		if(sum==n-1) break;
	}
	if(sum==n-1) printf("%d\n",ans);
	else printf("orz\n");
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
	
	sort(e+1,e+m+1);
	Kruskal();
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
struct qwq{
	int x,y,z;
	/*bool operator<(const qwq &a)const{
		return z<a.z;
	}*/
}e[N];
bool operator<(const qwq &a,const qwq &b){
	return a.z<b.z;
}

int ans,sum,f[N];
int n,m;
int getf(int a){
	if(f[a]==a) return a;
	return f[a]=getf(f[a]);
}
void Kruskal(){
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++){
		int fa=getf(e[i].x),fb=getf(e[i].y);
		if(fa!=fb){
			f[fa]=fb;
			ans+=e[i].z;
			sum++;
		}
		if(sum==n-1) break;
	}
	if(sum==n-1) printf("%d\n",ans);
	else printf("orz\n");
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
	
	sort(e+1,e+m+1);
	Kruskal();
	return 0;
}

另外,第一个程序中重载运算符那个const有啥用啊

2022/10/27 21:26
加载中...