```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#define LEN 10005
int N, M, K, p[LEN], size[LEN], ans, mx;
struct E {
int u, v, w;
} e[LEN];
bool cmp(E const &l, E const &r) {
return l.w < r.w;
}
int find_set(int x) {
if (x == p[x])
return x;
p[x] = find_set(p[x]);
return p[x];
}
void union_set(int x, int y) {
x = find_set(x), y = find_set(y);
if (size[x] > size[y])
std::swap(x, y);
p[x] = y;
size[y] += size[x];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
// std::freopen("input.txt", "r", stdin);
// std::freopen("output.txt", "w", stdout);
std::cin >> N >> M >> K;
if (K > N) {
std::cout << "No Answer\n";
return 0;
}
for (int i = 1; i <= M; i++) {
auto& [u, v, w] = e[i];
std::cin >> u >> v >> w;
}
for (int i = 1; i <= N; i++) {
p[i] = i;
size[i] = 1;
}
std::sort(e + 1, e + M + 1, &cmp);
mx = 1;
for (int i = 1; i <= M && mx <= N - K; i++) {
auto [u, v, w] = e[i];
if (find_set(u) != find_set(v)) {
ans += w;
union_set(u, v);
}
mx = std::max(mx, size[find_set(u)]);
}
if (mx != N - K + 1)
std::cout << "No Answer\n";
else
std::cout << ans << std::endl;
return 0;
}
```
by inawah @ 2023-09-02 11:46:54
数据:[#7](https://pastebin.com/EngbWGQM)
by inawah @ 2023-09-02 11:50:05
一看就是大佬 ~~你代码我看不懂~~,这个“size”能和我解释一下吗?(才学,不懂什么深奥的)
**总之,你错在“mx”没有在找到边后自加(个人理解)**
AC代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#define LEN 10005
int N, M, K, p[LEN], size[LEN], ans, mx;
struct E {
int u, v, w;
} e[LEN];
bool cmp(E const &l, E const &r) {
return l.w < r.w;
}
int find_set(int x) {
if (x == p[x])
return x;
p[x] = find_set(p[x]);
return p[x];
}
void union_set(int x, int y) {
x = find_set(x), y = find_set(y);
if (size[x] > size[y])
std::swap(x, y);
p[x] = y;
size[y] += size[x];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
// std::freopen("input.txt", "r", stdin);
// std::freopen("output.txt", "w", stdout);
std::cin >> N >> M >> K;
if (K > M) {
std::cout << "No Answer\n";
return 0;
}
for (int i = 1; i <= M; i++) {
auto& [u, v, w] = e[i];
std::cin >> u >> v >> w;
}
for (int i = 1; i <= N; i++) {
p[i] = i;
size[i] = 1;
}
std::sort(e + 1, e + M + 1, &cmp);
mx = 1;
for (int i = 1; i <= M && mx <= N - K; i++) {
auto [u, v, w] = e[i];
if (find_set(u) != find_set(v)) {
ans += w;
union_set(u, v);
mx++;
}
}
if (mx < N - K-1)
std::cout << "No Answer\n";
else
std::cout << ans << std::endl;
return 0;
}
```
by leiwenjin1234 @ 2023-10-04 19:53:36
@[leiwenjin1234](/user/921176)
就是这个并查集的深度(儿子数)吧
by Addrian @ 2023-10-18 08:38:28