Untitled
unknown
plain_text
24 days ago
1.5 kB
2
Indexable
Never
#include <iostream> #include <vector> #include <algorithm> #include <tuple> using namespace std; vector<tuple<int, int, int>> in_MST; struct DSU { vector<int> fa, sz; DSU(int n) { fa.resize(n + 1); sz.resize(n + 1, 1); for (int i = 0; i <= n; i++) fa[i] = i; } int find(int x) { return (fa[x] == x ? x : fa[x] = find(fa[x])); } bool unite(int a, int b) { a = find(a), b = find(b); if (a == b) return 0; if (sz[a] > sz[b]) swap(a, b); fa[a] = b; sz[b] += sz[a]; return 1; } }; signed main() { int n, m; cin >> n >> m; DSU dsu(n); vector<tuple<int, int, int>> edges(m); for (auto &[u, v, w] : edges) cin >> u >> v >> w; sort(edges.begin(), edges.end(), [](auto &a, auto &b) { return get<2>(a) < get<2>(b); }); for (auto &[u, v, w] : edges) { if (dsu.unite(u, v)) in_MST.emplace_back(make_tuple(u, v, w)); } long long ans = 1e18; for (auto &[a, b, c] : in_MST) { long long g = 0; DSU dsu(n); for (auto &[u, v, w] : edges) { if (a == u && b == v && c == w) continue; if (dsu.unite(u, v)) g += w; } ans = min(g, ans); } cout << ans << '\n'; }
Leave a Comment