题目大意是给你n个点的完全图,对于每两个点之间的边有两个权值,cost和len,求一个生成树,使得∑cost/∑len最小。

每条边cost的计算是这条边两端点的权值之差的绝对值。len的计算是两个点之间的距离。


01分数规划传送门:http://woodcoding.com/?id=172


我们可以先根据给出的数据求出每条边的cost和len,然后把每条边的权值设为cost-x*len跑生成树求和,最后判断。

(这个题我在输入数据时定区间比直接从范围定区间快了0.3s的样子)


地址:http://poj.org/problem?id=2728


输入数据定范围

代码:

(本题)

StatusAccepted
Time1391ms
Memory19940kB
Length1946
LangC++

(范围定区间)

StatusAccepted
Time1782ms
Memory24368kB
Length1900
LangC++


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
#define MP pair<int, int>
typedef long long LL;
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-5;
const int maxn=1005;
int x[maxn], y[maxn], h[maxn], vis[maxn], cost[maxn][maxn];
double len[maxn][maxn], val[maxn][maxn], dis[maxn];
int n;
bool Prim(double mid){
    double sum=0;
    int u=1;
    mem(vis, 0);
    for(int i=1;i<=n;i++)dis[i]=inf;
    vis[u]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            val[i][j]=cost[i][j]-mid*len[i][j];
        }
    }
    for(int i=1;i<n;i++){
        double small=inf;
        int now=-1;
        for(int j=1;j<=n;j++){
            if(vis[j])continue;
            dis[j]=min(dis[j], val[u][j]);
            if(dis[j]<small){
                small=dis[j], now=j;
            }
        }
        vis[now]=1;
        sum+=dis[now];
        u=now;
    }
    return sum>=0;
}
int main()
{
    while(~scanf("%d", &n)&&n){
        for(int i=1;i<=n;i++){
            scanf("%d%d%d", &x[i], &y[i], &h[i]);
        }
        double l=0, r=0, mid;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                cost[i][j]=cost[j][i]=abs(h[i]-h[j]);
                len[i][j]=len[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])*1.0+1.0*(y[i]-y[j])*(y[i]-y[j]));
                r=max(r, cost[i][j]/len[i][j]);
            }
        }
        while(r-l>eps){
            mid=(l+r)/2;
            if(Prim(mid))l=mid;
            else r=mid;
        }
        printf("%.3f\n", l);
    }
    return 0;
}