0分救助大佬,实在搞不懂
查看原帖
0分救助大佬,实在搞不懂
811016
ashore_楼主2022/11/9 19:25
#include <algorithm>
#include <cstdio>
#include <iostream>
#define MAX_N 0x3f3f3f
using namespace std;
int N, M, K;
struct op {
  int x, y, l;
} data_[MAX_N];
//par是并查集的数组,rak是每个结点的深度
int par[MAX_N], rak[MAX_N];
inline void init(int n) {
  for (int i = 1; i <= n; ++i) {
    par[i] = i;
    rak[i] = 0;
  }
}
int find(int x) {
  if (par[x] = x)
    return x;
  else
    return par[x] = find(par[x]);
};
void unit(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  if (rak[x] < rak[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rak[x] == rak[y]) ++rak[x];
  }
}
inline bool same(int x, int y) { return find(x) == find(y); };
//以上并查集代码
void solve() {
  //对数组进行排序,先连接权值较小的
  sort(data_ + 1, data_ + M + 1,
       [](op &x, op &y) noexcept -> bool { return y.l > x.l; });
  int ans = 0;
  for (int i = 1; i <= M; ++i) {
    op d = data_[i];
    //如果已经连上了就不操作,因为数组是升序的
    if (same(d.x, d.y)) continue;
    unit(d.x, d.y);
    ans += d.l;
    --K;//每合并一个棉花糖就多一个(也就是与目标值的差-1),当还需要一个棉花糖的时候就已经结束了
    if (K == 1) {
      printf("%d\n", ans);
      return;
    }
  }
  printf("No Answer\n");
}
int main() {
  scanf("%d %d %d", &N, &M, &K);
  init(N);
  for (int i = 1; i <= M; ++i) {
    scanf("%d %d %d", &data_[i].x, &data_[i].y, &data_[i].l);
  }
  solve();
  return 0;
}
2022/11/9 19:25
加载中...