[POJ 2728] Desert King

一、题目

点此看题

二、解法

典型的二分$+01$分数规划，我们分治一个比率$r$，那么我们看最小值能不能小于等于$r$，看式子：
$$\frac{\sum |z_u?z_v|}{\sum dis(u,v)}\le r$$$$\sum |z_u?z_v|?dis(u,v)\times r\le 0$$如果满足上述条件，那么我们就去找更小的答案，否者找大的。至于检查的时候我们就想让选出来的边的和最小，用$\mathtt{p}\mathtt{r}\mathtt{i}\mathtt{m}$跑一遍最小生成树就可以了，注意要预处理距离（因为根号运算很慢）

#include <cstdio>
#include <cmath>
const int M = 1005;
#define eps 1e-6//注意精度
#define db double
#define inf 1e9
int read()
{
    int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {
    if(c=='-') f=-1;}while(c>='0' && c<='9') {
    x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int n,vis[M];db ans,ds[M][M],d[M],x[M],y[M],z[M];
db Abs(db x)
{
    return x>0?x:-x;
}
db dis(int a,int b)
{
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}//nmsl,老子打掉一个开根 
db val(int a,int b,db r)
{
    return Abs(z[a]-z[b])-r*ds[a][b];
}
bool fuck(db r)
{
    db tmp=0;for(int i=1;i<=n;i++) d[i]=inf,vis[i]=0;d[1]=0;for(int k=1;k<=n;k++){
    db mn=inf;int u=0;for(int i=1;i<=n;i++)if(d[i]<mn && !vis[i]){
    u=i;mn=d[i];}if(mn==inf) break;tmp+=mn;vis[u]=1;for(int v=1;v<=n;v++){
    db t=val(u,v,r);if(!vis[v] && d[v]>t)d[v]=t;}}if(tmp>0) return 0;return 1;
}
void work(db l,db r)
{
    if(r-l<eps) return ;db mid=(l+r)/2;if(fuck(mid)){
    ans=mid;work(l,mid);}else work(mid,r);
}
signed main()
{
    while(~scanf("%d",&n) && n){
    ans=0;for(int i=1;i<=n;i++){
    scanf("%lf %lf %lf",&x[i],&y[i],&z[i]);}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)ds[i][j]=ds[j][i]=dis(i,j);//必须预处理，开根耗时间 work(0,40);printf("%.3f\n",ans);}
}