题目大意:
求最小方差生成树.N<=100,M<=2000,Ci<=100
题解:
首先我们知道这么一个东西:
- 一些数和另一个数的差的平方之和的最小值在这个数是这些数的平均值时取得
所以我们可以枚举这个平均数,然后计算所有边与该值的差的平方
然后扔下去跑一个最小生成树 然后我们通过枚举这个平均数发现这个平均数和答案的对应函数的图像是一个波形函数所以我们可以直接在这个波形图像上找函数最低点:
相应的就有
- 爬山算法
- 模拟退火
两种算法
所以我们可以先在全局用模拟退火然后在局部用爬山算法。
#include#include #include #include 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;}