poj2728|poj2728 Desert King poj2728DesertKing

大概题意：
每两个点中的边权有两个：一个是两点坐标的欧几里得距离（ horizontal distance），暂且成为ai,第二个是两点的海拔之差，称为bi.然后需要一个生成树使sum(ai)\sum(bi)最小。

这里可以引入分数规划：我们设ai\bi=k,那么ai-bi*k=0
我们只需要二分一个值mid，当ai-bi*mid=0时，这时的mid便是最优值。
对于每一个mid，将每一条边的边权都变为ai-bi*mid，然后求一个最小生成树，如果总长是0，说明mid是答案，如果总长>0说明mid小了，让mid变大，反之让mid变小。
但是！！你以为这样就完了吗？根本没有！！！

文章图片

文章图片

坑点:
1、这个点是一个完全图，也就是有足足n^2条边，我们使用的算法一定要尽力规避m，再见kruskal！，再见堆优化！甚至临界表，再见！我们必须要用没有堆优化，使用邻接矩阵的prim！
2、精度不能取0.0001或者0.001就ok了，必须要取到0.00001！
3、二分时r一定不能开大，开打一点都会T，开到100就行，不要怕错！！！
4、终极大坑，最后的输出不能用%lf,必须用%f,不要为我为什么！厂长是我表哥！！

#include #include #include #include #include #include #include #define REP(i,k,n)for(int i=k; i<=n; i++) #define in(a) a=read() #define MAXN 1000030 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1; for(; isdigit(ch); ch=getchar()) x=x*10+ch-'0'; return x*f; } int n; int x[1010],y[1010],d[1010]; int f[1010]; struct edge{ int u,v; double a,b; }old[10101010]; double map[1010][1010],dis[1010]; int vis[1010]; int total; inline double check(double k){ double sum=0; memset(dis,127,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(map,127,sizeof(map)); REP(i,1,total)map[old[i].v][old[i].u]=map[old[i].u][old[i].v]=old[i].a-k*old[i].b; dis[1]=0; for(int i=1; i<=n; i++){ double minn=2147483647; int v=-1; for(int j=1; j<=n; j++) if(vis[j]==0 && (v==-1 || dis[j]map[v][j]) dis[j]=map[v][j]; } return sum; } int main(){ while(cin>>n){ if(!n)break; total=0; REP(i,1,n)in(x[i]),in(y[i]),in(d[i]),x[i]++,y[i]++,d[i]++; REP(i,1,n) REP(j,1,i-1){ old[++total].a=abs(d[i]-d[j]); old[total].b=sqrt(abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j])); old[total].u=i,old[total].v=j; } double l=0,r=100.0,mid,k; while(r-l>0.00001){ mid=(l+r)/2; k=check(mid); if(k>0)l=mid; if(k<0)r=mid; if(k==0) break; } printf("%.3f\n",mid); } return 0; } /* 5 2 3 3 3 2 10 5 1 3 5 7 6 7 8 4 */

【poj2728|poj2728 Desert King】转载于:https://www.cnblogs.com/jason2003/p/10335821.html