poj2728 Desert King --- 01分数规划 二分水果。。
规划 --- 01 二分 分数 水果
2023-09-14 09:07:57 时间
这题数据量较大。普通的求MST是会超时的。
d[i]=cost[i]-ans*dis[0][i]
据此二分。
但此题用Dinkelbach迭代更好
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; #define N 1010 double mp[N][N],c[N][N],x[N],y[N],z[N],e[N][N],d[N]; int vis[N],n; inline double prim(double mid) { double tmp,ans=0; for(int i=0;i<n;i++) { vis[i]=0; for(int j=0;j<i;j++) e[i][j]=e[j][i]=c[i][j]-mid*mp[i][j]; } for(int i=1;i<n;i++) d[i]=e[0][i]; d[0]=0;vis[0]=1; for(int i=1;i<n;i++) { int p; tmp=100000000; for(int j=0;j<n;j++) { if(!vis[j]&&d[j]<tmp) { p=j; tmp=d[j]; } } ans+=tmp; vis[p]=1; for(int j=0;j<n;j++) { if(!vis[j]&&e[j][p]<d[j]) d[j]=e[j][p]; } } return ans; } int main() { int i,j; double le,ri,mid; while(scanf("%d",&n)&&n) { for(i=0;i<n;i++) scanf("%lf%lf%lf",&x[i],&y[i],&z[i]); for(i=0;i<n;i++) for(j=0;j<i;j++) { mp[i][j]=mp[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); c[i][j]=c[j][i]=z[i]>z[j]?z[i]-z[j]:z[j]-z[i]; } le=0;ri=1001;//不开心。。这样才干水过 while(ri-le>1e-5) { mid=(le+ri)/2.0; // printf("prim:%lf\n",prim(0,mid)); if(prim(mid)>0) le=mid; else ri=mid; } printf("%.3f\n",mid); } return 0; }
相关文章
- 动态规划之最长公共子序列
- 搭建一个小型网络-规划、设计、配置
- Leetcode0393: UTF-8 编码验证(medium, 动态规划)
- RL笔记:动态规划(2): 策略迭代
- 微信小程序----map路线规划
- Atitit uke各大事业部规划 约365个事业部
- AAtitit.随时间变色特效 ---包厢管理系统的规划titit.随
- Atitit.随时间变色特效 ---包厢管理系统的规划
- 【优化调度】基于改进遗传算法求解带时间窗约束多卫星任务规划(Matlab代码实现)
- matlab 动态规划逆序法及应用实例
- 《程序猿》约稿:在多任务的时间管理,规划的目标和任务分解
- HCIE-Cloud Computing LAB备考第二步:逐题攻破--第五题:规划--综合
- 强化学习原理及应用作业之动态规划算法【SYSU_2023SpringRL】