大学做视频网站设计,网页制作设计课设报告,wordpress图片并排,昆山外贸公司网站建设流程最优配对问题
jzoj 3420
题目大意#xff1a;
在平面上有n个点#xff0c;现在要把他们拼成n/2对#xff0c;拼接两个点的代价是他们的平面距离#xff0c;现在问代价总和最小是多少
输入样例
4
8730 9323
-3374 3929
-7890 -6727
1257 4689输出样例
20366.60数据范围…最优配对问题
jzoj 3420
题目大意
在平面上有n个点现在要把他们拼成n/2对拼接两个点的代价是他们的平面距离现在问代价总和最小是多少
输入样例
4
8730 9323
-3374 3929
-7890 -6727
1257 4689输出样例
20366.60数据范围
2N20
解题思路#1
用dfs每一次选1个数和当前数字匹配如果当前数字选过了就进入下一层
代码#1
#includecmath
#includecstdio
#define min(a,b) (a)(b)?(a):(b)
using namespace std;
int n,p[30];
double ans,x[30],y[30];
double dis(int a,int b){return sqrt((x[a]-x[b])*(x[a]-x[b])(y[a]-y[b])*(y[a]-y[b]));}//计算
void dfs(int dep,double sum)
{if (depn){ansmin(ans,sum);//尝试更新答案return;}if (sumans) return;//无法更新答案了if (p[dep]) dfs(dep1,sum);//选过就直接下一层else{for (int idep1;in;i)if (!p[i]){p[i]1;dfs(dep1,sumdis(dep,i));//选一个和它匹配的数p[i]0;}}
}
int main()
{scanf(%d,n);for (int i1;in;i)scanf (%lf %lf,x[i],y[i]);ans9999999999.99;dfs(1,0.0);printf(%.2lf,ans);
}解题思路#2
用bfs先造出一个状压模型然后用模型进行状压DP
代码#2
#includecmath
#includecstdio
#includecstring
#includeiostream
#define min(a,b) (a)(b)?(a):(b)
using namespace std;
int n,tail1,q[121];
double x[30],y[30],f[121];
int pd(int x,int y){return x(1y);}
double dis(int a,int b){return sqrt((x[a]-x[b])*(x[a]-x[b])(y[a]-y[b])*(y[a]-y[b]));}
void bfs()//制造模型
{q[1]0;int h,head0;while(headtail){hq[head];int in-1;for (;i0;--i)if (pd(h,i)) break;//找一个最高位的1for (int jn-1;ji;--j)//在最高位后面加1q[tail]h|(1j);}
}
void dp()
{for (int i1;itail;i){int sq[i];int jn-1;for (;j0;--j)if (!pd(s,j)) break;//找最高位的0for (int k0;kj;k)//找一个和它相匹配的数if (!pd(s,k))f[s|(1j)|(1k)]min(f[s|(1j)|(1k)],f[s]dis(j,k));//状压DP}
}
int main()
{scanf(%d,n);for (int i0;in;i)scanf(%lf %lf,x[i],y[i]);memset(f,0x7f,sizeof(f));f[0]0;bfs();dp();printf(%.2lf,f[(1n)-1]);//输出
}
