有一张点数为L边数为p的图，给出点权与边权({b_i})，定义边权({a_i})为连接边的两点的点权之差的绝对值，现在选出一棵生成树，使边上的a之和除以b最小，(2 ≤ L ≤ 1000)，(2 ≤ P ≤ 5000) 。
解
显然建出图来就是求最优比率生成树的问题，但是注意本张图为一完全图，于是使用prim，建边使用邻接矩阵，接下来照套路搞即可。
参考代码：
二分
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define il inline
#define ri register
#define db double
#define exact 0.000001
using namespace std;
bool is[2001];
int p[2001][3],head[2001],n;
db mini[2001],dis[2001],a[2001][2001],
b[2001][2001],c[2001][2001];
il db dfs(db,db);
il bool check(db);
template<class free>il free Abs(free);
int main(){
int i,j;;
while(scanf("%d",&n),n){
for(i=1;i<=n;++i)
scanf("%d%d%d",&p[i][0],&p[i][1],&p[i][2]);
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
b[i][j]=b[j][i]=sqrt(pow(p[i][0]-p[j][0],2.0)
+pow(p[i][1]-p[j][1],2.0)),
a[i][j]=a[j][i]=Abs(p[i][2]-p[j][2]);
printf("%.3lf
",dfs(0,100));
}
return 0;
}
il bool check(db s){
int i,j,k;db v,mst(0);
for(i=0;i<=n;++i)mini[i]=1e36;
for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)c[i][j]=c[j][i]=a[i][j]-b[i][j]*s;
memset(is,0,sizeof(is)),mini[1]=0;
for(i=1;i<=n;++i){
for(j=1,k=0;j<=n;++j)if(mini[j]<mini[k]&&!is[j])k=j;
for(is[k]|=true,mst+=mini[k],j=1;j<=n;++j)
if(mini[j]>c[k][j])
mini[j]=c[k][j];
}return mst>exact;
}
il db dfs(db l,db r){
db mid;
while(r-l>exact){
mid=(l+r)/2;
if(check(mid))l=mid+exact;
else r=mid-exact;
}return (l+r)/2;
}
template<class free>
il free Abs(free x){
return x<0?-x:x;
}
迭代
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define il inline
#define ri register
#define db double
using namespace std;
bool is[2001];
int p[2001][3],head[2001],n,pre[2001];
db mini[2001],dis[2001],a[2001][2001],
b[2001][2001],c[2001][2001];
il db check(db);
template<class free>il free Abs(free);
int main(){
int i,j;db r,ans;mini[0]=1e18;
while(scanf("%d",&n),n){
for(i=1;i<=n;++i)
scanf("%d%d%d",&p[i][0],&p[i][1],&p[i][2]);
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
b[j][i]=b[i][j]=sqrt(pow(p[i][0]-p[j][0],2.0)
+pow(p[i][1]-p[j][1],2.0)),
a[j][i]=a[i][j]=Abs(p[i][2]-p[j][2]);
r=100;while(true){
ans=check(r);
if(ans<r)r=ans;
else break;
}printf("%.3lf
",r);
}
return 0;
}
il db check(db s){
int i,j,k;db mom(0),son(0);
for(i=1;i<=n;mini[i]=1e18,++i)
for(j=i+1;j<=n;++j)
c[j][i]=c[i][j]=a[i][j]-b[i][j]*s;
mini[1]=0,pre[1]=1;
for(i=1;i<=n;++i){
for(j=1,k=0;j<=n;++j)
if(!is[j]&&mini[j]<mini[k])k=j;
son+=a[pre[k]][k],mom+=b[pre[k]][k];
for(is[k]|=true,j=1;j<=n;++j)
if(mini[j]>c[k][j])
mini[j]=c[k][j],pre[j]=k;
}return memset(is,0,sizeof(is)),son/mom;
}
template<class free>
il free Abs(free x){
return x<0?-x:x;
}