目录

• 题目
• 思路
• 代码

[2021.8集训Day10/JZOJ.3410]【GDOI2014模拟】Tree

题目

思路

我们枚举一个参考平均数(注意不是真正的平均数),把每条边按边权与参考平均数的差的绝对值从小到大排序,跑一遍Kruskal,即可求出对应的标准差:

double now_average;//参考平均数

struct EDGE {
	int u , v , c;
}ed[M];
bool cmp(EDGE a , EDGE b) {
	return fabs((double)a.c - now_average) < fabs((double)b.c - now_average);
}

bool choosed[M];
double GetDeviation() {
	UF::init();
	std::sort(ed + 1 , ed + m + 1 , cmp);
	std::memset(choosed , 0 , sizeof(choosed));
	
	double average;
	for(int i = 1 ; i <= m ; i++) {
		int u = ed[i].u , v = ed[i].v;
		if(UF::findroot(u) == UF::findroot(v))
			continue;
		UF::uni(ed[i].u , ed[i].v);
		choosed[i] = true;
		average += ed[i].c;
	}
	
	double deviation = 0;
	average /= (double)(n - 1);//真正的平均数
	for(int i = 1 ; i <= m ; i++)
		if(choosed[i])
			deviation += fabs(average - (double)ed[i].c) * fabs(average - (double)ed[i].c);
	
	return sqrt(deviation / (double)(n - 1));
}

不难想到, 若\(x=\text{参考平均数}\),\(f(x)=参考平均数对应的标准差\),\(f(x)\)应该是一条比较丝滑的曲线,因此,我用了模拟退火.其实直接一个一个枚举也行,不过模拟退火跑得巨快300ms内就可以出结果.

代码

这不是GMOJ的AC代码

同样的数据,本地A,洛谷云IDE A , GMOJ WA(雾)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
unsigned seed;

int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	seed *= re;
	return negt ? -re : re;
}

const int N = 110 , M = 2010;
struct EDGE {
	int u , v , c;
}ed[M];


const double delta_t = 0.993;
const double originT = 100;//初始温度没必要太大,因为c的范围小

int n , m;
double ans_average , ans_deviation = 1e10;


namespace UF {
	int fa[N];
	void init() {
		for(int i = 1 ; i <= n ; i++)
			fa[i] = i;
	}
	int findroot(int x) {
		return fa[x] == x ? x : (fa[x] = findroot(fa[x]));
	}
	inline void uni(int u , int v) {
		if(findroot(u) != findroot(v))
			fa[findroot(u)] = fa[v];
	}
}

double now_average = 50;
bool cmp(EDGE a , EDGE b) {
	return fabs((double)a.c - now_average) < fabs((double)b.c - now_average);
}
bool choosed[M];
int minc , maxc;
double GetDeviation() {
	UF::init();
	std::sort(ed + 1 , ed + m + 1 , cmp);
	std::memset(choosed , 0 , sizeof(choosed));
	
	double average;
	for(int i = 1 ; i <= m ; i++) {
		int u = ed[i].u , v = ed[i].v;
		if(UF::findroot(u) == UF::findroot(v))
			continue;
		UF::uni(ed[i].u , ed[i].v);
		choosed[i] = true;
		average += ed[i].c;
	}
	
	double deviation = 0;
	average /= (double)(n - 1);
	for(int i = 1 ; i <= m ; i++)
		if(choosed[i])
			deviation += fabs(average - (double)ed[i].c) * fabs(average - (double)ed[i].c);
	
	return sqrt(deviation / (double)(n - 1));
}
void simulate_anneal() {
	double average = ans_average;
	double t = originT;
	while(t > 1e-5) {//这个也没必要太小,否则答案没影响
		now_average = average + (rand() * 2 - RAND_MAX) * t;
		
		if(now_average < 0 || now_average > 100) {//优化下,温度的范围变小后,模拟退火可以跑得巨快.
			t *= delta_t;
			continue;
		}
		
		double now_deviation = GetDeviation();
		double DE = now_deviation - ans_deviation;
		if(DE < 0) {
			ans_average = average = now_average;
			ans_deviation = now_deviation;
		}
		else if(exp(-DE / t) * RAND_MAX > rand()) {
			average = now_average;
		}
		t *= delta_t;
	}
}
int main() {
	n = read() , m = read();
	for(int i = 1 ; i <= m ; i++) {
		ed[i].u = read() , ed[i].v = read() , ed[i].c = read();
	}
	
	std::srand(seed);
	
	for(int i = 1 ; i <= (m <= 20 ? 10 : 3) ; i++)
		simulate_anneal();
	std::printf("%.4f" , ans_deviation);
	return 0;
}