Untitled
unknown
c_cpp
a month ago
1.6 kB
6
Indexable
Never
#include <iostream> #include <vector> #include <tuple> #include <algorithm> using namespace std; int n, m; vector<tuple<int, int, int>> in_MST; struct DSU { int n; vector<int> pa, sz; DSU(int n) { pa.resize(n + 1), sz.resize(n + 1); for (int i = 1; i <= n; i++) pa[i] = i; }; int find_pa(int u); bool uni(int u, int v); }; int DSU::find_pa(int u) { return (pa[u] == u ? u : pa[u] = find_pa(u)); } bool DSU::uni(int u, int v) { int a = find_pa(u), b = find_pa(v); if (a == b) return 0; if (sz[a] > sz[b]) swap(a, b); pa[a] = b; sz[b] += sz[a]; return 1; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m; DSU dsu(n); vector<tuple<int, int, int>> E(m); for (auto &[a, b, c] : E) { cin >> a >> b >> c; } sort(E.begin(), E.end(), [](auto &a, auto &b) { return get<2>(a) < get<2>(b); }); long long ans = 0; for (auto &[a, b, c] : E) { if (dsu.uni(a, b)) { ans += c; in_MST.emplace_back(make_tuple(a, b, c)); } } for (auto &[a, b, c] : in_MST) { long long g = 0; DSU dsu(n); for (auto &[u, v, w] : E) { if (a == u && b == v && c == w) continue; if (dsu.uni(u, v)) g += w; } ans = min(ans, g); } cout << ans << '\n'; }
Leave a Comment