AcWing 348. 沙漠之王
原题链接
困难
作者:
追着你行走
,
2021-01-08 13:19:42
,
所有人可见
,
阅读 766
分析:
本题是0/1分数规划模型中的最优比率生成树问题,可以应用二分答案来做,设二分的值为mid,则此时每对点之间的权值可以看做:成本-mid*长度。
以此边权为基础构建一个无向图,并求出无向图的生成树,若生成树上边权之和非负,则令left=mid,否则令r=mid.
由于本题的点数为N=1000级别,而边数为$N^2$ ,因此用prim算法更优。时间复杂度为$O(N^2logN)$
C++ 代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
typedef long long ll;
const double eps=1e-6,inf=1e12;;
#define max(a,b) (a>=b?a:b)
#define min(a,b) (a>=b?b:a)
struct P{
double x,y,z;
}point[maxn];
inline double cost(int x,int y,double k){ //两个点之间的边权值
double ans=fabs(point[x].z-point[y].z);
P a=point[x],b=point[y];
return ans-k*sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)) ;//权值
}
int n,tot,vis[maxn];
double d[maxn];
bool check(double mid){ //二分答案中的check函数
double ans=0;
fill(d,d+1+n,inf); //double 类型数组的初始化为inf
memset(vis,0,sizeof(vis));
d[1]=0;//运行prim
for(int i=1;i<=n;i++){
int x=0;
for(int j=1;j<=n;j++){
if(!vis[j]&&(x==0||d[j]<d[x])) x=j;
}
vis[x]=1;
ans+=d[x];//生成树中权值
for(int y=1;y<=n;y++){
if(!vis[y])
d[y]=min(d[y],cost(x,y,mid) ) ;
}
}
return ans>=0.0;
}
int main(){
while(cin>>n,n){
for(int i=1;i<=n;i++)
cin>>point[i].x>>point[i].y>>point[i].z;
double left=0,right=10000001.0;
while(right>eps+left){
double mid= (left + right) / 2 ;
if(check(mid)) left = mid;
else right = mid ;
}
printf("%.3lf\n",(left+right)/2 );
}
return 0;
}
二分复杂度O(log n) prim复杂度O($n^2$)
为什么时间复杂度不是N^3log(right)????