jzoj 3420 最优配对问题

Description

平面上有n个点P1,P2,…,Pn,你的任务是把它们配成n/2对(n是偶数)，使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。n<=20,|xi|,|yi|<=10000。

Input

第一行输入n(2到20之间的偶数)
接下来n行，每行输入两个整数表示xi,yi。|xi|,|yi|<=10000。

Output

输出最小配对距离。答案保留两位小数。

Sample Input

4

8730 9323

-3374 3929

-7890 -6727

1257 4689

Sample Output

20366.60

Data Constraint

2<=N<=20

Solution

从这题开始状压的学习。
发现这个数据范围很小，考虑用二进制进行状压。
设一个状态f[i]，表示把i转化为二进制之后，为1的位已配对好，所得的最大值。
强制选编号小的与编号大的进行配对。
每次枚举一个i
找到i中为1的第一位，设为x 另外再枚举一个y
则可得f[i]=max(f[i],f[i^((1<<(x-1))^(1<<(y-1)]+dis(x,y));

Code

#include 
#include 
#include 
#include 
#define inf 1000000007
#define fo(i,a,b) for (i=a;i<=b;i++) 
using namespace std;
double f[2000000];
int x[25],y[25];
double dis(int i,int j) {return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main(){//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);int n,i,j;scanf("%d",&n);fo(i,1,n) scanf("%d%d",&x[i],&y[i]);fo(i,1,((1<1)) {f[i]=inf;for (j=1;j<=n;j++) if ((i&(1<<(j-1)))!=0) break;for (int k=j+1;k<=n;k++) if ((i&(1<<(k-1)))!=0)f[i]=min(f[i],f[i^(1<<(j-1))^(1<<(k-1))]+dis(k,j));
}printf("%.2lf",f[(1<1]);
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！