?? pku2726最優(yōu)比率生成樹(shù).txt
字號(hào):
/*
David剛剛成為一個(gè)沙漠之國(guó)的國(guó)王。為了贏得民心,他決定建一個(gè)路網(wǎng)覆蓋整個(gè)王國(guó)
以方便各個(gè)村莊去打水。村莊只要能連接到他的首都就能有水了。作為這個(gè)國(guó)家權(quán)利和智慧的象征,
他需要以一種更合理的方式來(lái)建設(shè)這些路。
經(jīng)過(guò)幾天的學(xué)習(xí),他最終制訂出了他的計(jì)劃。他希望這些路每英里的平均花費(fèi)最小。
換句話說(shuō),就是希望這些路的總成本和總長(zhǎng)度的比值最小。他只需要建能讓所有村莊的村民順利打水的必經(jīng)之路,
也就是說(shuō)每個(gè)村莊只能有一條路通向首都。
他的工程師勘察了整個(gè)王國(guó),記錄了每個(gè)村莊的坐標(biāo)和海拔。每條路連接兩個(gè)村莊的路必須是一條直線,
并且是水平的。由于每個(gè)村莊都有不同的海拔,他們決定在每條路上建一個(gè)提水用的升降機(jī),
每條路的長(zhǎng)度是兩個(gè)村莊的水平距離,而花費(fèi)就是兩個(gè)村莊的高度差。需要注意的是,每個(gè)村莊都有不同的高度,
不同的路不能共享他們的升降機(jī)。建設(shè)的這些路可以相交,而且沒(méi)有超過(guò)兩個(gè)村莊在同一條直線上。
作為國(guó)王David的首席科學(xué)家兼程序員,你被要求找出建設(shè)這些路的最優(yōu)方案。
輸入
多組數(shù)據(jù),每組數(shù)據(jù)第一行是一個(gè)數(shù)字N(2<=N<=1000),表示村莊的個(gè)數(shù)。接下來(lái)N行描述村莊,
每行有3個(gè)數(shù)字x,y,z(0 <= x, y < 10000, 0 <= z < 10000000)。
(x,y)表示這個(gè)村莊的坐標(biāo),z是這個(gè)村莊的海拔。第一個(gè)村莊是首都。N=0表示數(shù)據(jù)結(jié)束。
輸出
每組數(shù)據(jù)輸出一個(gè)小數(shù),表示總成本和總長(zhǎng)度的最小的比值(結(jié)果精確到小數(shù)點(diǎn)后3位)
*/
#include <iostream>
#include <math.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define inf 1.5*100000000
using namespace std;
const int maxn=1001;
double G[maxn][maxn];
double dis[maxn][maxn];
double h[maxn];
int n;
double prim()
{
int i,j;
bool s[maxn];
double close[maxn];
memset(s,false,sizeof(s));
for(i=0;i<n;i++) close[i]=inf;
s[0]=1;
for(i=1;i<n;i++) close[i]=G[0][i];
double total=0;
for(i=1;i<n;i++){
int idx;
double mn=inf;
for(j=1;j<n;j++) if(!s[j] && close[j]<mn){
idx=j;
mn=close[j];
}
s[idx]=1;
total+=close[idx];
for(j=1;j<n;j++) if(!s[j] && close[j]>G[idx][j]) close[j]=G[idx][j];
}
return total;
}
// 給定當(dāng)前比例r,建新圖
void buildG(double r)
{
int i,j;
for(i=0;i<n;i++) for(j=0;j<n;j++) G[i][j]=0;
//printf("G with r=%.3lf\n",r);
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
G[i][j]=G[j][i]=fabs(h[i]-h[j])-r*dis[i][j];
//printf("%.2lf ",G[i][j]);
}
//printf("\n");
}
// printf("\n");
}
void read()
{
int i,j;
double x[maxn],y[maxn];
//scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%lf%lf%lf",&x[i],&y[i],&h[i]);
}
for(i=0;i<n;i++) dis[i][i]=0;
for(i=0;i<n;i++) for(j=i+1;j<n;j++){
dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
//printf("%d %d %.2lf\n",i,j,dis[i][j]);
}
}
void solve()
{
// discuss 里的上下界
double l=0,h=31,mid=(h+l)/2;
buildG(mid);
//printf("%.3lf\n",prim());
// 二分搜索r_star使得用r_star建立的圖的最小生成樹(shù)權(quán)為0
while(true){
double res=prim();
if(fabs(res)<1e-5) break;
if(res<0) h=mid;
else l=mid;
mid=(h+l)/2;
buildG(mid);
}
printf("%.3lf\n",mid);
}
int main()
{
while(scanf("%d",&n) && n!=0){
read();
solve();
}
return 0;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -