首页 > 其他 > 详细

最优点配对问题(紫书)

时间:2017-08-20 11:09:23      阅读:34      评论:0      收藏:0      [点我收藏+]

标签:cnblogs   包含   math   blog   ostream   最小花费   bsp   最小   for   

题目大意:对于n个点,每个点可以用一个三维坐标来描述,将这n个点两两配对,使得所有点对的最大距离最小。

 

题解:

设dp[S],表示将集合S中的点配对的最小花费,那么我们可以找到集合S中最大的元素i,在从集合S,任取一个元素j,那么dp[S]肯定是从不包含i,j,但其余元素都有的集合转移过来的,既dp[S]=min(dp[S],dis(i,j)+dp[S^(1<<i)^(1<<j)]);

 

代码:(由于没有oj提交,所以正确性不保证,如果发现错误麻烦留言提醒)

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
#include<cmath>
#define inf 1e15
using namespace std;
double dp[1<<22],x[30],y[30],z[30];
int n;

double dis(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])+(z[a]-z[b])*(z[a]-z[b]));
}

double minn(double x,double y){
    if(x<y) return x;
    return y;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i]>>z[i];
    for(int S=1;S<(1<<n);S++){
        int i,j;
        dp[S]=inf;
        for(i=n-1;i>=0;i--) if((1<<i)&S) break;
        for(j=i-1;j>=0;j--)
        if((1<<j)&S){
            dp[S]=minn(dp[S],dis(i,j)+dp[S^(1<<i)^(1<<j)]);
        }
    }
    printf("%.3f",dp[(1<<n)-1]);
}
 

 

最优点配对问题(紫书)

标签:cnblogs   包含   math   blog   ostream   最小花费   bsp   最小   for   

原文:http://www.cnblogs.com/renjianshige/p/7398972.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号