最小生成树会多样的情况是：两个或多个边等长且连通同样的两个并查集块。
所以可以跑一遍克鲁斯卡尔，每次把当前等长的边数出来，注意不要边找边并查，因为有一部分边是正常跑生成树我们也不会要他的，这种直接跳了；还有一些，是因为你选择了第一个边，然后并在一起了，这时扫到后面的边时他自然会被抛弃。而这种比较委屈的、因为先来后到而被抛弃的边的个数，正是本题答案。如果贪心地并查地话，无法区分这个是本来就跳的，还是我们要找的。
1 const int maxn = 2e5 + 5; 2 int n, m, f[maxn], ans; 3 struct Edge { 4 int u, v, cost; 5 6 bool operator < (const Edge& rhs) const { 7 return cost < rhs.cost; 8 } 9 }e[maxn]; 10 11 inline int getf(int v) { return v == f[v] ? v : f[v] = getf(f[v]); } 12 13 int main() { 14 read(n), read(m); 15 rep(i, 1, n) f[i] = i; 16 rep(i, 1, m) { 17 read(e[i].u); 18 read(e[i].v); 19 read(e[i].cost); 20 } 21 sort(e + 1, e + 1 + m); 22 for (int i = 1, j; i <= m; i = j) { 23 for (j = i; j <= m && e[j].cost == e[i].cost; j++); 24 int cnt = 0; 25 rep(k, i, j - 1) { 26 if (getf(e[k].u) != getf(e[k].v)) 27 cnt++; 28 } 29 rep(k, i, j - 1) { 30 if (getf(e[k].u) != getf(e[k].v)) { 31 f[getf(e[k].u)] = getf(e[k].v); 32 cnt--; 33 } 34 } 35 ans += cnt; 36 } 37 writeln(ans); 38 return 0; 39 }
原文：https://www.cnblogs.com/AlphaWA/p/10620671.html