1 条题解

  • 0
    @ 2025-10-8 16:57:01
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1100;
    const double eps=1e-8;
    struct node{double x,y,z;}p[N];
    int n;
    double a[N][N],b[N][N],d[N];int v[N];//a为高度,b为长度
    double dis(node n1,node n2){return sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));}
    bool prim(double L){
        memset(d,0x7f,sizeof(d));d[1]=0;//memset double 0 为 0,0x7f为无穷大。其他都不能用。 
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++){
            int x=0;
            for(int j=1;j<=n;j++){
                if(!v[j]&&(x==0||d[j]<d[x]))x=j;
            }
            v[x]=1;
            for(int y=1;y<=n;y++)
                if(!v[y]&&d[y]>a[x][y]-L*b[x][y])
                    d[y]=a[x][y]-L*b[x][y];
        }
        double ans=0;for(int i=2;i<=n;i++)ans+=d[i];
        return ans>=0.0;
    }
    int main(){
        while(scanf("%d",&n)!=EOF&&n)
    	{
            for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
            for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
            {
            	a[i][j]=abs(p[i].z-p[j].z);
    			b[i][j]=dis(p[i],p[j]);
            }
            double l=0,r=1e9,mid;
            while(r-l>eps)
    		{
                mid=(l+r)/2;
                if(prim(mid))l=mid;
                else r=mid;
            }
            printf("%.3lf\n",l);
        }
        return 0;
    }
    
    • 1

    *【01分数规划+最小生成树】沙漠之王[POJ2728]

    信息

    ID
    1436
    时间
    10000ms
    内存
    64MiB
    难度
    8
    标签
    递交数
    146
    已通过
    20
    上传者