北京賽區的經典題目，最優比率生成樹，傳說中樓哥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;
}