poj2728 Desert King（最小生成树+01分数规划=最优比率生成树）

题意

n个点完全图，每个边有两个权值,求分数规划要求的东西的最小值。

（n<=1000)

题解

心态炸了。

堆优化primT了。

普通的就过了。

我再也不写prim了！！！！

咳咳

最优比率生成树板子题。

公式不是很难推吧。

 1 #include<iostream>
 2 #include<cmath>
 3 #include<iomanip>
 4 #include<string.h>
 5 const int N=1050;
 6 const int inf=0x7fffffff;
 7 using namespace std;
 8 int n,book[N];
 9 double x[N],y[N],h[N],w2[N][N],w1[N][N],ans,dis[N];
10 double prim(double mid){
11     double mn;
12     ans=0;
13     memset(book,0,sizeof(book));
14     int now;
15     for(int i=2;i<=n;i++) 
16         dis[i]=w2[1][i]-w1[1][i]*mid;
17     for(int i=2;i<=n;i++){
18         mn=inf;
19         for(int j=2;j<=n;j++)
20             if(!book[j]&&mn>dis[j]){
21                 now=j;
22                 mn=dis[j];
23             }
24         book[now]=1;
25         ans+=mn;
26         for(int j=2;j<=n;j++)
27             if(!book[j]&&dis[j]>w2[now][j]-w1[now][j]*mid)
28                 dis[j]=w2[now][j]-w1[now][j]*mid;
29     }
30     return ans;
31 }
32 double kf(int i,int j){
33     return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
34 }
35 int main(){
36     while(scanf("%d",&n)&&n){
37         for(int i=1;i<=n;i++){
38             scanf("%lf%lf%lf",&x[i],&y[i],&h[i]);
39             for(int j=1;j<i;j++){
40                 w1[i][j]=w1[j][i]=kf(i,j);
41                 w2[i][j]=w2[j][i]=abs(h[i]-h[j]);
42             }
43         }
44         double l=0.0,r=1000.0,mid;
45         while(r-l>1e-5){
46             mid=(l+r)/2;
47             if(prim(mid)>=0) l=mid;
48             else r=mid;
49         }
50         printf("%.3lf
",l);
51     }
52 }

View Code