原题链接:蓝桥杯算法提高VIP-最小方差生成树
在生成树权值和范围内跑 Kruskal 求方差,取最小即可 。在某 OJ 过了,这边有毒。
参考代码:
#include <bits/stdc++.h> const int Inf = 0x3F3F3F3F; typedef long long LL; using namespace std; namespace IO { inline LL read() { LL o = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); } return o * f; } inline char recd() { char o; while ((o = getchar()) != 'Q' && o != 'D'); return o; } } using namespace IO; const int SIZE = 1E5 + 7; struct EDGES { int from, to, w; double p; } E[SIZE << 1]; int F[SIZE], N, M, Case; bool cmp_(EDGES X, EDGES Y) { return X.w < Y.w; } bool _cmp(EDGES X, EDGES Y) { return X.p < Y.p; } int Fnd(int pos) { return pos == F[pos] ? pos : F[pos] = Fnd(F[pos]); } void INIT_F() { for (int pos = 1; pos <= N; pos++) F[pos] = pos; } double Kruskal(int AVG) { double AVGs = double(AVG) / (N - 1); INIT_F(); for (int pos = 1; pos <= M; pos++) E[pos].p = (E[pos].w - AVGs) * (E[pos].w - AVGs); sort(E + 1, E + 1 + M, _cmp); int Sum = 0; double ans = 0; for (int pos = 1, Tot = 0, U, V; pos <= M; pos++) { U = Fnd(E[pos].from), V = Fnd(E[pos].to); if (U != V) { Sum += E[pos].w, ans += E[pos].p; F[U] = V, Tot++; } if (Tot == N - 1) break; } return Sum == AVG ? ans : Inf; } int main() { while (true) { N = read(), M = read(); if (!M && !N) return 0; for (int pos = 1; pos <= M; pos++) E[pos].from = read(), E[pos].to = read(), E[pos].w = read(); sort(E + 1, E + 1 + M, cmp_); int MAX = 0, MIN = 0; double ans = Inf; INIT_F(); for (int pos = 1, u, v; pos <= M; pos++) { u = Fnd(E[pos].from), v = Fnd(E[pos].to); if (u != v) MIN += E[pos].w, F[u] = v; } INIT_F(); for (int pos = M, u, v; pos; pos--) { u = Fnd(E[pos].from), v = Fnd(E[pos].to); if (u != v) MAX += E[pos].w, F[u] = v; } /*cout << MAX << MIN << endl;*/ for (int AVG = MIN; AVG <= MAX; AVG++) ans = min(ans, Kruskal(AVG)); printf("Case %d: %.2f\n", ++Case, ans / (N - 1)); } }
0.0分
3 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复