Prim 79pts求助
查看原帖
Prim 79pts求助
549027
__JiCanDuck__楼主2023/10/22 22:15
#include <iostream>
#include <algorithm>
#define Fr first
#define Se second
#define Mp make_pair
#define PII pair<int, pair<int, int>>

using namespace std;

const int kMaxN = 1005, kMaxM = 2e5 + 5;

int n, m, fa[kMaxN], cnt;
long long ans;
PII a[kMaxM];

int findRt(int x) {
  return fa[x] == x ? x : fa[x] = findRt(fa[x]);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) fa[i] = i;
  for (int i = 1, x, y, z; i <= m; i++) {
    cin >> x >> y >> z;
    a[i] = Mp(z, Mp(x, y));
  }
  sort(a + 1, a + m + 1, [](PII x, PII y) { return x.Fr < y.Fr; });
  for (int i = 1; i <= m && cnt < n; i++) {
    if (findRt(a[i].Se.Fr) != findRt(a[i].Se.Se)) {
      fa[findRt(a[i].Se.Fr)] = findRt(a[i].Se.Se);
      cnt++;
      ans += a[i].Fr;
    }
  }
  if (cnt != n - 1) cout << "orz";
  else cout << ans;
  return 0;
}

来源于一个神奇的小朋友,要我调,感觉没什么问题(我不会告诉你就是我自己)

2023/10/22 22:15
加载中...