首页 > 代码库 > 紫书---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点集配对问题