首页 > 代码库 > 紫书---P61点集配对问题
紫书---P61点集配对问题
紫书---P61点集配对问题
-------状压DP
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define INF 0x3f3f3f3fstruct Point{ double x,y,z;}p[20+2];int n;double dp[(1<<20)+10]; //dp[j]表示j对应状态(0为未配对,1为配对了)的最小距离和double dist(int i,int j){ return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)+(p[i].z-p[j].z)*(p[i].z-p[j].z));}void solve(){ int i,j,k,MAX=1<<n; for(i=0;i<MAX;i++) { dp[i]=1e10; } dp[0]=0; for(j=0;j<MAX;j++) { for(i=0;i<n;i++) { if(j&(1<<i)) break; } for(k=i+1;k<n;k++) { if(j&(1<<k) { dp[j]=min(dp[j],dp[(j&(~(1<<i)))&(~(1<<k))]+dist(i,k)); } } } printf("%lf\n",dp[MAX-1]);}int main(){ while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) { scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z); } solve(); } return 0;}
紫书---P61点集配对问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。