CF437D The Child and Zoo 题解

~~我在怀疑这道题的颜色~~ 来补一下模拟赛的T1 我就按着模拟赛的数据范围给出一步一步的做法。 把模拟赛数据范围贴上来（ 对于10%的测试数据，满足$2 \leq n \leq 10 , n - 1 \leq m \leq 20$ 对于30%的测试数据，满足$2 \leq n \leq 200 , n - 1 \leq m \leq 1000$ 对于50%的测试数据，满足$2 \leq n \leq 1000 , n - 1 \leq m \leq 20000$ 对于100%的测试数据，满足$2 \leq n \leq 100000 , n - 1 \leq m \leq 1000000$ $ 0 \leq a_i \leq 100000 ,1 \leq x_i,y_i \leq n,(x_i \neq y_i)$，保证是连通图且没有重边。 解法1： 暴力枚举点跑n遍$Floyd$ 分数：10pts（这时间复杂度有点惨 解法2： 随便想想珂以暴力枚举两点枚举所有路径 分数：30pts 解法3： 从每个点跑$BFS$ 分数：50pts 解法4： 并查集 通过观察可得所有的路径必在最大生成树上。 证明：若有一条满足题意的连接$x$与$y$的路径，且不在最大生成树上，那么由于这条路径不在最大生成树上，必定至少有一条边的边权$ \leq $最大生成树上的边权，那么选择最大生成树上的路径不会更劣 $Q.E.D.$ 然后$Kruskal$跑最大生成树统计答案即可。 分数：100pts 细节见代码。 ```cpp #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; const int maxm = 1e6 + 5; typedef long long ll; ll n, m, ans; int val[maxn], s[maxn], fa[maxn], siz[maxn]; int hd[maxn], tot, vis[maxn]; struct edge { int nxt, to; } ed[maxm << 1]; int findfa(int x) { return fa[x] == x ? x : fa[x] = findfa(fa[x]); } bool cmp(int a, int b) { return val[a] > val[b]; } void addedge(int x, int y) { ed[++tot] = (edge){hd[x], y}; hd[x] = tot; } signed main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; siz[i] = 1, i++) scanf("%d", &val[s[i] = fa[i] = i]); sort(s + 1, s + n + 1, cmp); for (int i = 1, a, b; i <= m; i++) { scanf("%d%d", &a, &b); addedge(a, b); addedge(b, a); } for (int u = 1; u <= n; u++) { ll res = 0; for (int i = hd[s[u]]; i; i = ed[i].nxt) { int v = ed[i].to; if (!vis[v]) continue; int p = findfa(s[u]), q = findfa(v); if (p == q) continue; res += 1ll * siz[p] * siz[q]; fa[p] = q; siz[q] += siz[p]; } ans += 1ll * res * val[s[u]]; vis[s[u]] = 1; } printf("%lf\n", ans * 2.0 / (n * (n - 1))); return 0; } ```