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

模拟赛时候不会状压，直接用搜索。为了避免重复枚举使用了hash防止重复计算，但WA掉了。

希望大佬帮调，或指出下我思路的错误。

Code：

	#include<bits/stdc++.h>
	#define ll long long
	using namespace std;
	int n,x[30],y[30];double ans=1969952581;bool f[30];
	int he_z=0,yhh_z=0;
	map<pair<int,int>,double>Map;
	double dfs(int u,int cnt,double s,int last,int he,int yhh){
		he+=u,yhh^=u;
		if(cnt%2==0){
			s+=sqrt((x[u]-x[last])*(x[u]-x[last])+(y[u]-y[last])*(y[u]-y[last]));
			if(Map.count(make_pair(he_z-he,yhh_z^yhh))){
				double ls=s+Map[make_pair(he_z-he,yhh_z^yhh)];
				ans=min(ls,ans);
				return ls;
			}
//			cout<<u<<endl;
		}
		if(cnt==n) {
			ans=min(s,ans);return s;
		}
//		cout<<s<<endl;
		double Min=1969952581;
		for(int i=2;i<=n;i++){
			if(!f[i]){
//				cout<<u<<" "<<i<<endl;
				f[i]=1;
				Min=min(Min,dfs(i,cnt+1,s,u,he,yhh));
				f[i]=0;
			}
		}
		if(cnt%2==0)Map.insert(make_pair(make_pair(he_z-he,yhh_z^yhh),Min-s));
//		cout<<he_z-he <<" "<<Min<<" "<<u<<" "<<cnt<<endl;
		return Min;
	}
	int main(){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
		f[1]=1;
		for(int i=1;i<=n;i++) he_z+=i,yhh_z^=i;
		dfs(1,1,0,1,1,1);
		printf("%.2lf",ans);
		return 0; 
	} 

wa数据：

in：

8
-4953 3708
-5654 -5345
-9480 8644
-8144 153
311 9144
7300 8678
6882 -4330
-4859 -5221

out：

28400.17

我的答案： 21511.25