[DarkBZOJ3754] Tree之最小方差树

前言

感觉如果不讲做法应该要想上好一会,甚至可能做不出来。

题目

DarkBZOJ

讲解

拿到这道题很有可能没什么思路,我们就从暴力入手。

先把标准差的公式写出来:

\[\sqrt{\frac{\sum_{0\le i<n}(a_i-\overline{a})^2}{n}} \]

对于这道题,显然我们知道生成树是 \(n-1\) 条边,而且外面的根号其实不影响相对大小,所以我们去掉这些东西( \(a_i\) 为边权):

\[\sum (a_i-\overline{a})^2 \]

显然我们如果知道了 \(\overline{a}\) 的大小,就可以通过最小生成树算法求出上面这个东西的最小值,可惜我们不知道。

但我们真的不能知道吗?

写出它的表达式:\(\overline{a}=\frac{\sum a_i}{n-1}\) ,显然 \(\overline{a}\) 由 \(\sum a_i\) 决定,我们发现 \(\sum a_i\) 最多不过 \(10^4\),直接枚举即可。

但是这还不够,如果你枚举一次做一次 \(\tt Kruskal\),发现复杂度达到了 \(O(cnm\log_2m)\),是有问题的。

其实我们只需要一次排序,枚举一次的时候用双指针维护一下当前情况下权值 \((a_i-\overline{a})\) 最小,且原始权值 \(a_i\) 小于和大于平均值的边,并不难实现。

于是复杂度就是 \(O(m\log_2m+cnm)\)。

我真不想说脏话。(摊手

代码

不懂戳我
//12252024832524
#include <cmath>
#include <cstdio>
#include <cstring> 
#include <algorithm>
#define TT template<typename T>
using namespace std;

typedef long long LL;
const int MAXN = 105;
const int MAXM = 2005;
const int INF = 0x3f3f3f3f;
int n,m;
double ans = INF;

LL Read()
{
	LL x = 0,f = 1; char c = getchar();
	while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1) 
{
	if(x < 0) x = -x,putchar('-');
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

struct edge
{
	int u,v,w;
	bool operator < (const edge &px)const{
		return w < px.w;
	}
}e[MAXM];

int f[MAXN];
int findSet(int x){if(x^f[x])f[x]=findSet(f[x]);return f[x];}
void unionSet(int u,int v){f[findSet(u)] = findSet(v);}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = Read(); m = Read();
	for(int i = 1;i <= m;++ i) e[i].u = Read(),e[i].v = Read(),e[i].w = Read();
	sort(e+1,e+m+1);
	e[0].w = -INF; e[m+1].w = INF;
	for(int C = 1;C <= 100*(n-1);++ C)
	{
		for(int i = 1;i <= n;++ i) f[i] = i;
		int cnt = n-1,s = 0; double av = C / (n-1.0),cur = 0;
		int r = upper_bound(e+1,e+m+2,edge{0,0,(int)ceil(av)}) - e;
		int l = r-1;
		while(cnt)
		{
			while(l > 0 && findSet(e[l].u) == findSet(e[l].v)) --l;
			while(r <= m && findSet(e[r].u) == findSet(e[r].v)) ++r;
			double L = av-e[l].w,R = e[r].w-av;
			if(L < R) cur += L*L,s += e[l].w,unionSet(e[l].u,e[l].v),--l;
			else cur += R*R,s += e[r].w,unionSet(e[r].u,e[r].v),++r;
			--cnt;
		}
		if(s == C) ans = Min(ans,sqrt(cur/(n-1)));
	}
	printf("%.4f",ans);
	return 0;
}
上一篇:AcWing夏季每日一题--最长公共子序列


下一篇:[ABC200E] Patisserie ABC 2