算法
(最小全域木、KrusKal法、并查集) $O(M)$
显然不需要删掉负边。
先对每条边按边权大小从小到大排序,然后按边权从小到大扫描每条边,若当前边的两端点所对应的 group
是连通的且为正边,则可以删去这条边;若不连通或当前边为负边,则合并这两个 group
。
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::pair;
using ll = long long;
using P = pair<int, int>;
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, P>> es;
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
es.emplace_back(c, P(a, b));
}
sort(es.begin(), es.end());
ll ans = 0;
dsu d(n);
for (auto [c, e] : es) {
auto [a, b] = e;
if (c < 0 or !d.same(a, b)) {
d.merge(a, b);
}
else {
ans += c;
}
}
cout << ans << '\n';
return 0;
}