• 应用
• 登录
• 注册

# 求助，WA 掉 9 个点

@yyfcpp 2018-03-14 00:10 回复

//【P2330】[SCOI2005] 繁忙的都市 - 洛谷 - 10
#include <iostream>
#include <algorithm>

struct Edge {
int u;
int v;
int c;
Edge(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {}
Edge() {}
};

constexpr int kMaxN = 300;
constexpr int kMaxM = 50000;

Edge e[kMaxM + 5];
int fa[kMaxN + 5];

int find(int x) {
if (x == fa[x])
return x;
return fa[x] = find(fa[x]);
}

void merge(int u, int v) {
u = find(u);
v = find(v);
fa[v] = u;
}

int main() {
int n, m;
std::cin >> n >> m;
for (int i = 1; i <= n; ++i) // 又一次忘记初始化并查集
fa[i] = i;
for (int i = 1; i <= m; ++i) {
int u;
int v;
int c;
std::cin >> u >> v >> c;
e[i] = Edge(u, v, c);
}
std::sort(e + 1, e + m + 1, [](const Edge &e1, const Edge &e2) {
return e1.c < e2.c;
});

int cnt = 0;
for (int i = 1; i <= m; ++i) {
if (find(e[i].u != find(e[i].v))) {
merge(e[i].u, e[i].v);
if (++cnt == n - 1) {
std::cout << cnt << " " << e[i].c << std::endl;
return 0;
}
}
}
}
@小闸蟹 2018-03-14 06:45 回复

@Arashi丶 2018-03-14 07:31 回复
return fa[x] = find(fa[x]);

fa[x] = find (fa[x]);
return fa[x];
@Chjka 2018-03-14 09:36 回复

if (find(e[i].u != find(e[i].v)))

@小闸蟹 2018-03-14 09:53 回复