在生成树权值和范围内跑 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.0分

3 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论