kruscal对边进行排序时产生的疑惑
查看原帖
kruscal对边进行排序时产生的疑惑
183738
_volcano_楼主2021/8/25 20:20

先放代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 2e5 + 9;

struct Edge{
	int u, v, w;
}e[N];

Edge make_edge(int u, int v, int w){
	Edge cur;
	cur.u = u, cur.v = v, cur.w = w;
	return cur;
}
bool cmp(Edge a, Edge b){
	return a.w < b.w;
}

int n, m, f[N];
long long ans, cnt;
int find(int x){
	if(f[x] == x) return x;
	else return f[x] = find(f[x]);
}


int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) f[i] = i;
	int x, y, z;
	for(int i = 1; i <= m; i++){
		scanf("%d%d%d", &x, &y, &z);
		e[i] = make_edge(x, y, z);
	}
	sort(e + 1, e + 1 + m, cmp);
	for(int i = 1; i <= m; i++){
		int u = e[i].u, v = e[i].v, w = e[i].w;
		if(find(u) != find(v)){
			f[find(u)] = find(v);
			ans += w;
			cnt++;
		}
	}
	if(cnt < n - 1) printf("orz");
	else printf("%lld", ans);
	
	return 0;
}

上面的代码是正确的,但是如果吧cmp函数改一下

bool cmp(Edge a, Edge b){
	return a.w <= b.w;
}

即把<<改成了\le,这样就从ACAC变成了两个RERE加两个TLETLE,求问这是为什么

2021/8/25 20:20
加载中...