poj 2728 Desert King (최 적 비율 생 성 트 리)
1928 단어 des
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iomanip>
using namespace std;
const int maxn=1005;
const double eps=1e-6;
const double inf=0xffffffff;
struct node{
double x,y,h;
}no[maxn];
int n;
bool visited[maxn];
double weight[maxn][maxn],c[maxn][maxn],d[maxn][maxn];
double up,down;
double dis(node &a,node &b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void creattree(int n,double r)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
weight[i][j]=c[i][j]-r*d[i][j];
}
}
void prime()
{
up=0.0;down=0.0;
memset(visited,0,sizeof(visited));
int index;
int pre[maxn];
double dist[maxn];
visited[1]=1;
for(int i=0;i<n;i++)
{
dist[i]=weight[1][i];
pre[i]=1;
}
for(int i=0;i<n;i++)
{
double mmimum=inf;
for(int j=0;j<n;j++)
{
if(!visited[j]&&dist[j]<mmimum)
{
mmimum=dist[j];
index=j;
}
}
visited[index]=1;
up+=c[pre[index]][index];
down+=d[pre[index]][index];
for(int i=0;i<n;i++)
{
if(!visited[i]&&weight[index][i]<dist[i])
{
dist[i]=weight[index][i];
pre[i]=index;
}
}
}
}
int main()
{
while(scanf("%d",&n),n)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf",&no[i].x,&no[i].y,&no[i].h);
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
c[i][j]=fabs(no[i].h-no[j].h);
d[i][j]=dis(no[i],no[j]);
}
double r=30.0,ans=30.0;
while(1)
{
creattree(n,r);
prime();
r=up/down;
if(fabs(r-ans)<=eps)break;
else ans=r;
}
printf("%.3lf
",ans);
//cout<<fixed<<setprecision(3)<<ans<<endl;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
열거 기술 ~ 열거에 Describe 속성을 추가하고 열거 요소에 대한 설명 정보를 출력합니다이것은 열거된 공통 속성 클래스입니다. 평범한 매거 열거 요소에 대한 설명 정보를 출력합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.