【POJ2728】Desert King（分数规划）

题面

vjudge

翻译：

有\(n\)个点，每个点有一个坐标和高度

两点之间的费用是高度之差的绝对值

两点之间的距离就是欧几里得距离

求一棵生成数，使得单位距离的费用最小

题解

使得\(\sum cost/\sum dis\)最小

这是分数规划问题

二分答案\(K\)

如果\(K\)满足，则有

\(\sum cost-K\sum dis\leq 0\)

定义生成树边权为\(cost-K·dis\)

做最小生成树检查答案即可。

因为是稠密图，使用\(Prim\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define sqr(x) (1.0*(x)*(x))

#define RG register

#define MAX 1111

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,x[MAX],y[MAX],z[MAX];

double dis[MAX];

double len[MAX][MAX],cost[MAX][MAX],g[MAX][MAX];

bool vis[MAX];

bool check(double mid)

{

	for(int i=0;i<=n;++i)dis[i]=1e20,vis[i]=false;

	dis[1]=0;double tot=0;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			g[i][j]=cost[i][j]-mid*len[i][j];

	for(int i=1;i<=n;++i)

	{

		int u=0;

		for(int j=1;j<=n;++j)if(!vis[j]&&dis[j]<dis[u])u=j;

		vis[u]=true;tot+=dis[u];

		for(int j=1;j<=n;++j)

			if(!vis[j])

				dis[j]=min(dis[j],g[u][j]);

	}

	return tot<=0;

}

int main()

{

	while(n=read())

	{

		for(int i=1;i<=n;++i)x[i]=read(),y[i]=read(),z[i]=read();

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j)

				len[i][j]=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])),cost[i][j]=abs(z[i]-z[j]);

		double l=0,r=1e5;

		while(r-l>=1e-5)

		{

			double mid=(l+r)/2;

			if(check(mid))r=mid;

			else l=mid;

		}

		printf("%.3f\n",l);

	}

	return 0;

}