poj 2728 Desert King (최 적 비율 생 성 트 리)

ACM 문제 집:https://blog.csdn.net/weixin_39778570 / article / details / 83187443 도 론:https://blog.csdn.net/weixin_제목 링크:http://poj.org/problem?id=2728
제목 설명
데 이 비 드 대 제 는 막 사막 국가의 국왕 이 되 었 다.국민 의 존중 을 얻 기 위해 그 는 전국 각지 에 경 로 를 건설 하여 모든 마을 에 물 을 보 내기 로 결정 했다.그의 수도 마을 과 연 결 된 마을 은 물 을 공급 할 것 이다.국 가 를 통치 하 는 통치자 와 지혜 의 상징 으로서 그 는 가장 우아 한 방식 으로 경 로 를 세 워 야 한다.
며칠 간 의 공 부 를 거 쳐 그 는 마침내 자신의 계획 을 생각해 냈 다.그 는 매 마일 통로 의 평균 원 가 를 최저 로 낮 추 기 를 희망 한다.채널 의 총 원가 와 총 길이 의 비율 을 최소 화해 야 한 다 는 얘 기다.그 는 필요 한 경 로 를 만들어 모든 마을 로 물 을 보 내 는 것 은 모든 마을 을 수도 로 연결 하 는 방법 밖 에 없다 는 뜻 이다.
그의 엔 지 니 어 는 이 나 라 를 조사 하고 마을 마다 위치 와 해발 고 도 를 기록 했다.모든 경 로 는 반드시 두 마을 사이 로 직통 하고 수평 으로 건설 해 야 한다.두 마을 마다 해발 고도 가 다 르 기 때문에 그들 은 두 마을 사이 의 모든 수로 에 수직 적 인 양수기 가 필요 하 다 는 결론 을 내 렸 다. 물 을 끌 어 올 릴 수도 있 고 물 을 내 릴 수도 있다.수로 의 길 이 는 두 마을 사이 의 수평 거리 다.통로 의 원 가 는 승강기 의 높이 다.너 는 모든 마을 이 서로 다른 해발 고도 에 있 고 서로 다른 경로 로 승강 기 를 함께 사용 할 수 없다 는 것 을 알 아야 한다.경 로 는 안전하게 교차 할 수 있 고 세 마을 이 같은 노선 에 있 지 않다.
데 이 비 드 왕 의 수석 과학자 이자 프로그래머 로 서 당신 은 통 로 를 구축 하 는 가장 좋 은 해결 방안 을 찾 아야 합 니 다.
입력
몇 가지 테스트 용례 가 있다.모든 테스트 용례 는 숫자 N (2 < = N < = 1000) 을 포함 하 는 한 줄 에서 시작 하 는데 이것 이 바로 마을 의 수량 이다.다음 N 줄 의 모든 줄 에는 x, y, z (0 < = x, y < 100000 < = z < 1000000) 세 개의 정수 가 포함 되 어 있 습 니 다.(x, y) 는 마을 의 위치 이 고 z 는 높이 이다.첫 번 째 마을 은 수도 다.N = 0 의 테스트 용례 가 입력 을 끝내 고 처리 해 서 는 안 됩 니 다.
출력
모든 테스트 용례 에 대해 출력 한 줄 은 10 진 수 를 포함 하 는데 이것 은 채널 의 총 지출 이 전체 길이 에 대한 최소 비율 이다.이 숫자 는 소수점 뒤의 세 자리 까지 반올림 해 야 한다.
분석 하 다.
최소 생 성 트 리 한 그루 를 요구 해 s u m (c o s t) / s u m (l e n) sum (cost) / sum (len) sum (cost) / sum (cost) / sum (sum (cost) / sum (len) / sum (cost) / sum (len) sum (cost) / sum (len) / sum (len) = ans = = = > s u m (c o s t) - s u m (c o s t) - s u m (l e n) ∗ a n s = 0 sum (cost) - sum (len) * ans= 0 sum (cost) - 0 − (cost) - (cost) - 0 sum (cost) - 0 sum (cost) - 0 sum (cost sum (len) ∗ ans = 0 = = > s u m (c o s t)[i] − l e n [i] ∗ a n s) = 0 sum (cost [i] - len [i] * ans) = 0 sum (cost [i] − len [i] ∗] ∗ ans) = 0 그래서 우 리 는 이분 답 을 할 수 있다. s u m (c o s t [i] − l e n [i] ∗ a n s) > 0 sum (cost [i] - len [i] * ans) > 0 sum (cost [i] − len [i] ∗ ans)> 0 은 ans 가 작 다 는 것 을 설명 합 니 다. 그렇지 않 으 면 ans 가 크다 는 것 을 설명 합 니 다. 이 그림 은 완전한 그림 이기 때문에 prim 알고리즘 을 우선 고려 합 니 다. 이 알고리즘 은 먼저 점 이 나무 에 있 는 것 을 확인 한 다음 에 이 나무 에서 가장 가 까 운 점 을 찾 아 나무 에 합 친 다음 에 이 방금 합 친 점 을 사용 하여 그 가 나무의 최소 거 리 를 업데이트 하고 모든 점 이 나무 에 합 쳐 질 때 까지 합 니 다.
code

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=1005,INF=0x3f3f3f3f;
const double eps = 1e-6;
struct node{
	int x,y,z;
}a[N];
int n;
double d[N][N],c[N][N],cost[N][N],dis[N];
bool v[N];
double dist(int i, int j){
	return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
}
bool ok(double mid){
	fo(i,1,n){
		fo(j,i,n){
			if(i==j)c[i][j]=INF;
			else c[i][j] = c[j][i] = cost[i][j] - mid*d[i][j]; //    
		}
	}
	fo(i,1,n)dis[i] = INF;
	memset(v, 0, sizeof(v));
	dis[1] = 0; // prim        
	double ans = 0;
	while(1){
		int x = 0;
		fo(i,1,n)
			if(!v[i] && (!x || dis[x]>dis[i])) x = i;
		if(!x)break;
		v[x] = 1;
		ans += dis[x]; //         
		//          
		fo(i,1,n) dis[i] = min(dis[i], c[x][i]); 
	}
	return ans>0; //   mid   
}
int main(){
	while(scanf("%d",&n)&&n){
		double L=0,R=0;
		fo(i,1,n){
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); 
		}
		fo(i,1,n){
			fo(j,1,n){
				d[i][j] = d[j][i] = dist(i,j);
				cost[i][j] = cost[j][i] = abs(a[i].z - a[j].z);
				R += cost[i][j];
			}
		}
		while(R-L>=eps){
			double mid = (L+R)/2;
			if(ok(mid)){
				L = mid;
			}else R = mid;
		}
		printf("%.3f
", L);
	}
	return 0;
}