题目链接: https://acm.uestc.edu.cn/problem/ji-jie-jie-dai-xue-hua-hua/description
分析:
这种类型的题似乎有个名字叫最优比率生成树。
简单来说,就是对所求的式子进行变形,使得一边为0,然后采取二分的办法逼近答案。
一开始看数据范围,以为出题人把二分做法卡死了,只能使用迭代。
迭代的原理,我也不是很清楚。大概就是使用上一次的答案,来作为这次最小生成树的边权的因子,这样子可以更快的逼近答案。
因为自己写kruskal比较熟练,然后顺手写了个kruskal,结果被出题人说了。
然后仔细想了想,这种完全图中,确实prim比kruskal快得多,代码跑得快完全是因为迭代更快,如果是二分可能炸。
最终的复杂度无法估计,因为迭代的次数无法确定……
代码:
#include <iostream> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cstdio> #include <iomanip> using namespace std; const int INF = 0x3f3f3f3f; /////////////////////////// int par[1000]; int ranks[1000]; void init(int n) { for(int i=0;i<n;i++) { par[i]=i; ranks[i]=0; } } int find(int x) { if(par[x]==x) return x; else return par[x]=find(par[x]); } void unite(int x,int y) { x=find(x);y=find(y); if(x==y)return; if(ranks[x]<ranks[y]) { par[x]=y; } else { par[y]=x; if(ranks[x]==ranks[y])ranks[x]++; } } bool same(int x,int y) { return find(x)==find(y); } struct edge { int u,v; double height,dis,num; edge(){} edge(int _u,int _v,double _height,double _dis) { u=_u;v=_v;height=_height;dis=_dis; } }edges[500005]; bool cmp(const edge &a,const edge &b) { return a.num<b.num; } int x[1000],y[1000],z[1000]; int n,tot=0,pos; double k,k0=1.0,hsum,dsum; void diedai() { while(1) { k=k0;hsum=0.0;dsum=0.0;pos=0; init(n); for(int i=0;i<tot;++i) { edges[i].num=edges[i].height-k*edges[i].dis; } sort(edges,edges+tot,cmp); for(int i=0;i<n-1;) { if(same(edges[pos].u,edges[pos].v)) { ++pos;continue; } else { unite(edges[pos].u,edges[pos].v); hsum+=edges[pos].height; dsum+=edges[pos].dis; ++i;++pos; } } k0=hsum/dsum; if(fabs(k-k0)<0.000001) break; } } //////// int main() { //ios::sync_with_stdio(false); cin.tie(0); scanf("%d",&n); for(int i=0;i<n;++i) { scanf("%d%d%d",&x[i],&y[i],&z[i]); } for(int i=0;i<n;++i) { for(int j=i+1;j<n;++j) { edges[tot++]=edge(i, j, (double)abs(z[i]-z[j]), sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) ) ); } } diedai(); printf("%.3f",k0); return 0; }