bzoj 3754: Tree之最小方差树 模拟退火+随机三分
2024-10-19 19:27:22
题目大意:
求最小方差生成树.N<=100,M<=2000,Ci<=100
题解:
首先我们知道这么一个东西:
- 一些数和另一个数的差的平方之和的最小值在这个数是这些数的平均值时取得
所以我们可以枚举这个平均数,然后计算所有边与该值的差的平方
然后扔下去跑一个最小生成树
然后我们通过枚举这个平均数发现这个平均数和答案的对应函数的图像是一个波形函数
所以我们可以直接在这个波形图像上找函数最低点:
相应的就有
- 爬山算法
- 模拟退火
两种算法
所以我们可以先在全局用模拟退火然后在局部用爬山算法。
然而还是每三组数据就Wa一次
然后发现这样的话极限数据只需要0.8s,还有1.2s可以用
所以可以在全局再三分找函数最低点.
随机化左右端点然后再三分.
随机化22次端点极限数据可以跑到1.3s
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 128;
const int maxm = 2048;
const double eps = 1e-10;
const double det = 0.99;
struct Node{
int u,v,bed;
double d;
bool friend operator < (const Node &a,const Node &b){
return a.d < b.d;
}
}G[maxm];
int fa[maxn];
inline int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
int n,m;
inline double work(double mid){
for(int i=1;i<=n;++i) fa[i] = i;
for(int i=1;i<=m;++i) G[i].d = (G[i].bed - mid)*(G[i].bed - mid);
sort(G+1,G+m+1);
int cnt = 0;double sum = 0;
for(int i=1;i<=m;++i){
int x = find(G[i].u);
int y = find(G[i].v);
if(x != y){
sum += G[i].d;
fa[x] = y;
if(++cnt == n-1) break;
}
}
return sqrt(sum/(n-1));
}
inline double ran(){
return (1.0*rand())/1000.0;
}
double ans = 1e10,ans_p;
inline double f(double mid){
double x = work(mid);
if(ans > x){
ans = x;
ans_p = mid;
}return x;
}
int main(){
srand(2333);
read(n);read(m);
int minn = 0x7f7f7f7f,maxx = -0x7f7f7f7f;
for(int i=1;i<=m;++i){
read(G[i].u);
read(G[i].v);
read(G[i].bed);
minn = min(minn,G[i].bed);
maxx = max(maxx,G[i].bed);
}
double l = minn,r = maxx,nx,t,val_nx;
double T = 50.0,nw = (l+r)/2,val_nw;
while(T > eps){
nx = ( rand() % 2 == 0 ? -1 : 1)*ran()*T;
t = val_nw - (val_nx = f(nx));
if(t > 0 || exp(t/T) >= ran() ){
nw = nx;
val_nw = val_nx;
}
T *= det;
}
while(r-l > eps){
double midx = (l+l+r)/3;
double midy = (l+r+r)/3;
double x = f(midx);
double y = f(midy);
if(x < y) r = midy;
else l = midx;
}
ans = min(ans,f(l));
int num = 22;
while(num--){
double l = minn + rand()*ran()*0.1;
double r = maxx - rand()*ran()*0.1;
if(l > r) swap(l,r);
while(r-l > eps){
double midx = (l+l+r)/3;
double midy = (l+r+r)/3;
double x = f(midx);
double y = f(midy);
if(x < y) r = midy;
else l = midx;
}ans = min(ans,f(l));
}
printf("%.4lf\n",ans);
getchar();getchar();
return 0;
}
最新文章
- Java学习之反射机制及应用场景
- WordPress一键部署网站
- Junit很少出现的一个问题 No tests found matching ...
- chaper3_exerise_Uva1368_DNA序列
- 【BZOJ】2697: 特技飞行
- centos命令
- ubuntu如何开启root,如何启用Ubuntu中root帐号
- 1.ssh访问限制
- 译文:Javascript-function&#39;s return
- classpath多个包添加
- Selenium webdriver firefox 路径设置问题
- Excel导入mysql数据库
- fatal error LNK1112: module machine type &#39;x64&#39; conflicts with target machine type &#39;X86&#39;
- 一个简单链表的C++实现(二)
- Amazon Hiring Campus 2013 - Final 6
- AngularJS中的$http.post与jQuery.post的区别
- hadoop单机环境搭建
- http://codeforces.com/contest/535/problem/C
- 微信小程序 页面跳转传递数据
- 浅谈jquery事件命名空间