简要概过: 将所有边排序,从小到大依次取边, 如果添加这条边不会形成环，那么添加这条边. 环的判断:利用并查集(如果是一个大家庭里面的成员,那么不能再加了,we are family) 题目:洛谷 p3366
const int MAXSIZE = 2*1e5 + 11; struct Edge { int from, to, wh; Edge() :from(0), to(0), wh(0) {} Edge(int f,int t,int w) :from(f), to(t), wh(w) {} bool operator < (const Edge& other) { return wh < other.wh; } }; Edge edges[MAXSIZE]; int n, m,nCount = 0; int unit[MAXSIZE] = { 0 }; int GetFamily(int a) { return a == unit[a] ? a : unit[a] = GetFamily(unit[a]); } void AddFamily(int a, int b) { int fa = GetFamily(a); int fb = GetFamily(b); if (fa != fb) unit[fa] = unit[fb]; } int Kruskal() { int ans = 0; for (int i = 1; i <= n; ++i) unit[i] = i; sort(edges, edges + nCount); for (int i = 0; i < m; ++i) { int f = edges[i].from; int t = edges[i].to; if (GetFamily(f) != GetFamily(t)) { AddFamily(f, t); ans += edges[i].wh; } } return ans; } int main() { cin >> n >> m; int a, b, c; for (int i = 0; i < m; ++i) { cin >> a >> b >> c; edges[nCount++] = Edge(a, b, c); } int ret = Kruskal(); cout << ret << endl; return 0; }