蓝桥杯算法提高VIP-最小方差生成树 （C++代码）

        在生成树权值和范围内跑 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));
	}
}