更好的阅读体验:http://www.abmcar.top/archives/template-kruskal
git仓库链接:https://github.com/abmcar/ACM/tree/master/template
templateclass Kruskal { public: int find(int x) { if (x == father[x]) return x; father[x] = find(father[x]); return father[x]; } Kruskal(int _n) : n(_n) { father.resize(n + 1); ans = 0; for (int i = 1; i <= n; i++) father[i] = i; } void insert(T x, T y, T z) { edges.push_back({x, y, z}); } void solve() { sort(edges.begin(), edges.end()); for (int i = 0; i < (int)edges.size(); i++) { int f1 = find(edges[i].from); int f2 = find(edges[i].to); if (f1 == f2) continue; ans += edges[i].val; father[f1] = f2; cnt++; } } int get() { if (cnt != n - 1) return -1; return ans; } private: struct Edge { T from, to, val; bool operator<(Edge b) const { return val < b.val; } }; vector edges; vector father; int n, cnt; T ans; };
食用样例:
int n, m; cin >> n >> m; //初始化构造 Kruskalkru(n); for (int i = 1; i <= m; i++) { int t1, t2, t3; cin >> t1 >> t2 >> t3; //插入新边 kru.insert(t1, t2, t3); } //求解 kru.solve(); //获取结果 if (kru.get() == -1) cout << "impossible" << endl; else cout << kru.get() << endl;
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)