yhylivedream @ 2024-05-22 11:12:18
RT,比题解慢一百毫秒。
#include <bits/stdc++.h>
using namespace std;
using Ppi = pair<pair<int, int>, int>;
const int kMaxN = 5005, kMaxM = 2e5 + 5;
Ppi e[kMaxM];
int n, m, cnt, ans, w[kMaxN], fa[kMaxN], vis[kMaxM];
int F(int x) {
return fa[x] == x ? x : fa[x] = F(fa[x]);
}
void Record(int x, int y) { //x号边更新w[y]
(!w[y] || (e[x].second != e[w[y]].second && e[x].second < e[w[y]].second) ||
(e[x].second == e[w[y]].second && x < w[y])) && (w[y] = x);
}
int main() {
cin >> n >> m, iota(fa + 1, fa + n + 1, 1);
for (int i = 1; i <= m; i++) {
cin >> e[i].first.first >> e[i].first.second >> e[i].second;
}
for (w[0] = 1; w[0];) {
fill(w, w + n + 1, 0);
for (int i = 1; i <= m; i++) {
!vis[i] && F(e[i].first.first) != F(e[i].first.second) &&
(Record(i, F(e[i].first.first)), Record(i, F(e[i].first.second)), 0);
}
for (int i = 1; i <= n; i++) {
if (w[i] && !vis[w[i]]) {
w[0] = 1, cnt++, ans += e[w[i]].second;
vis[w[i]] = 1, fa[F(e[w[i]].first.first)] = F(e[w[i]].first.second);
}
}
}
cnt == n - 1 ? cout << ans : cout << "orz";
}
by oMin0 @ 2024-05-22 11:34:20
@yhylivedream 鉴定为 cin 没关同步流。
by yhylivedream @ 2024-05-22 11:47:41
@oMin0 破案了,关了同步流就快了