poj2728 最小比率生成树——01分数规划

题目大意：

有n个村庄，村庄在不同坐标和海拔，现在要对所有村庄供水，

只要两个村庄之间有一条路即可，建造水管距离为坐标之间的欧几里德距离，费用为海拔之差，

现在要求方案使得费用与距离的比值最小，很显然，这个题目是要求一棵最优比率生成树。

————————————————————————————————————

这是一道最优比率生成树的题目，是个很明显的0-1分数规划，设每条边代价为ci,距离为di

那么题目要求(∑(ci*xi))/(∑(di*xi))的最小值 xi∈{0,1}

我们进行一波转换

z=(∑(ci*xi))-r'*(∑(di*xi))，其中z是左边这个式子的最小值

由于di为正数，xi为非负数，所以

r'>r 时 z(r')<0

r'=r 时 z(r')=0

r'<r 时 z(r')>0

那么二分这个最小值，将这个式子化成xi(ci-r'*di)的形式，每条边的权值变成ci-r'*di

对于这些边，求一棵最小生成树，MST的值即为z(r')

这样问题就解决了QAQ（注：！这里输出要%.3f 不能lf ！！！我错了五次就在这里

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=1e4+7;
const double inf=1e15;
int n;
int v[M][M];
int x[M],y[M],w[M],vis[M];
double d[M],map[M][M];
double calc(int s1,int s2){return sqrt(1.0*(x[s1]-x[s2])*(x[s1]-x[s2])+1.0*(y[s1]-y[s2])*(y[s1]-y[s2]));}
double prim(double k){
    double sum=0;
    memset(vis,0,sizeof(vis));
    d[1]=0; vis[1]=1;
    for(int i=2;i<=n;i++) d[i]=(double)v[1][i]-k*map[1][i];
    for(int i=2;i<=n;i++){
        double mn=inf;
        int h=0;
        for(int j=2;j<=n;j++) if(!vis[j]&&mn>d[j]) mn=d[j],h=j;
        sum+=mn; d[h]=0; vis[h]=1;
        for(int j=2;j<=n;j++) if(!vis[j]&&((double)v[h][j]-k*map[h][j])<d[j]) d[j]=(double)v[h][j]-k*map[h][j];
    }
    return sum;
}
int main()
{
    while((scanf("%d",&n)!=EOF)&&n){
        for(int i=1;i<=n;i++) scanf("%d %d %d",&x[i],&y[i],&w[i]);
        for(int i=1;i<=n;i++) 
            for(int j=i+1;j<=n;j++) map[i][j]=map[j][i]=calc(i,j),v[i][j]=v[j][i]=abs(w[i]-w[j]);
        double l=0.0,r=100000.0;
        while(r-l>1e-7){
            double mid=(l+r)/2;
            if(prim(mid)>=0) l=mid;
            else r=mid;
        }printf("%.3f
",r);
    }
    return 0;
}

View Code

poj2728 最小比率生成树——01分数规划

相关推荐