POJ - 2728 Desert King 最小生成树 + 01分数规划-白红宇的个人博客

发布日期：2021-09-25 23:57:52 浏览次数：6 分类：技术文章

本文共 1438 字，大约阅读时间需要 4 分钟。

题意：给定n个点，他们之间有两个权值，一个是距离，一个是高度差，让后求联通所有点的最小花费比例 ( 高度差/距离 )，01分数规划的模板题，二分最小比例，让后把边权变为 h - x * d ，做一遍最小生成树，看是否 <= 0即可。

因为是个稠密图，所以用prim比较好，用克鲁斯卡尔会 t 掉。

prim的没优化版本的复杂度也挺高的，二分上界改大点也可能 t 。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-5;int n;double g[N][N],g1[N][N],g2[N][N],dis[N];bool st[N];struct Node{ int x,y; int z;}a[N];double get_dis(int i,int j){ int dx=a[i].x-a[j].x; int dy=a[i].y-a[j].y; return sqrt(dx*dx+dy*dy);}bool check(double x){ for(int i=0;i<=n;i++) dis[i]=INF*2,st[i]=false; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=g2[i][j]-x*g1[i][j]; double cos=0.0; for(int i=0;i
                
                 dis[j])) t=j; if(i) cos+=dis[t]; st[t]=true; for(int j=1;j<=n;j++) dis[j]=min(dis[j],g[t][j]); } return cos<=0;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); while(cin>>n&&n) { for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g1[i][j]=get_dis(i,j),g2[i][j]=fabs(a[i].z-a[j].z); double l=0.0,r=1e9,mid; while(r-l>eps) { mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } printf("%.3f\n",r); } return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/106344218 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：树链板子

下一篇：P2184 贪婪大陆线段树 + 区间覆盖

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章