先放代码
#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;
}
即把<改成了≤,这样就从AC变成了两个RE加两个TLE,求问这是为什么