北京赛区的经典题目，最优比率生成树，传说中楼哥1A的G题。。。
什么是最优比率生成树呢？说白了很简单，已知一个完全图，每条边有两个参数（b和c），求一棵生成树，使(∑xi×ci)/(∑xi×bi)最小，其中xi当第i条边包含在生成树中时为1，否则为0。其实也可以看成一个0，1的整数规划问题。
我的做法是LRJ《算法艺术与信息学竞赛》中介绍的二分，详细的证明请看书，这里只是简单的介绍一下核心的方法：
1.首先找出这个比率的最小值和最大值 front,rear
2.求mid=(front+reat)/2
3.用 ci-mid*bi 重新构图
4.求出新图的最小生成树权值之和
5.如果权值等于0,mid就是我们要求的比率，结束。如果权值>0,front=mid,如果权值<0,rear=mid,跳回2继续循环。
不过这个算法对精度的要求比较高，我用0.001就错了，0.00001超时，只有0.0001AC,汗
另外时间效率也不高，3000MS的题，耗去了2500MS，看来这个算法还是有待改进。
下面是我的代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define MAX 1001
#define INF 1000000000
struct node
{
double x,y,h;
}dot[MAX];
inline double dis(double x1,double y1,double x2,double y2)
{
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) );
}
double graph[MAX][MAX];
inline void creat(int n,double l)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
graph[i][j]=fabs(dot[i].h-dot[j].h)-l*dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
}
}
}
inline double prim(double graph[MAX][MAX],int n)
{
bool visit[MAX]={0};
int mark;
double dis[MAX];
double ans=0;
int i,j;
visit[1]=true;
for(i=1;i<=n;i++)
dis[i]=graph[1][i];
for(i=1;i<n;i++)
{
int minnum=INF;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<=minnum)
{
minnum=dis[j];
mark=j;
}
}
visit[mark]=true;
ans+=dis[mark];
for(j=1;j<=n;j++)
{
if(!visit[j]&&graph[mark][j]<dis[j])
dis[j]=graph[mark][j];
}
}
return ans;
}
int main()
{
int i,j;
int n;
double res;
while(scanf("%d",&n))
{
if(n==0)
break;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&dot[i].x,&dot[i].y,&dot[i].h);
}
double front,rear;
front=0;
rear=100;//这个地方有点悬。。。
double mid;
double pre=0.0;
while(front<=rear)
{
mid=(front+rear)/2;
creat(n,mid);
res=prim(graph,n);
if(fabs(res-pre)<=0.0005)
break;
else if(res>0.0005)
front=mid;
else
rear=mid;
}
printf("%.3lf\n",mid);
}
return 0;
}———————————————————————传说中的分割线————————————————————————————
终于在今天下午 使用迭代法将此题优化到282MS，呵呵 这名字让我又想起了数值分析。。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define MAX 1001
#define INF 1000000000
struct node
{
double x,y,h;
}dot[MAX];
inline double dis(double x1,double y1,double x2,double y2)
{
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) );
}
double graph[MAX][MAX];
double c[MAX][MAX];
double s[MAX][MAX];
inline void creatcs(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
c[i][j]=fabs(dot[i].h-dot[j].h);
s[i][j]=dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
}
}
}
inline void creat(int n,double l)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
graph[i][j]=c[i][j]-l*s[i][j];
}
}
}
double sumc;
double sums;
inline void prim(double graph[MAX][MAX],int n)
{
sumc=0;
sums=0;
bool visit[MAX]={0};
int mark;
int pre[MAX];
double dis[MAX];
int i,j;
visit[1]=true;
for(i=1;i<=n;i++)
{
dis[i]=graph[1][i];
pre[i]=1;
}
for(i=1;i<n;i++)
{
int minnum=INF;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<=minnum)
{
minnum=dis[j];
mark=j;
}
}
visit[mark]=true;
sumc+=c[pre[mark]][mark];
sums+=s[pre[mark]][mark];
for(j=1;j<=n;j++)
{
if(!visit[j]&&graph[mark][j]<dis[j])
{
dis[j]=graph[mark][j];
pre[j]=mark;
}
}
}
}
int main()
{
int i,j;
int n;
while(scanf("%d",&n))
{
if(n==0)
break;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&dot[i].x,&dot[i].y,&dot[i].h);
}
creatcs(n);
double prerate=30.0;
double rate=30.0;
while(true)
{
creat(n,rate);
prim(graph,n);
rate=sumc/sums;
if(fabs(rate-prerate)<0.001)
break;
prerate=rate;
}
printf("%.3lf\n",rate);
}
return 0;
}