最優配對問題

jzoj 3420

題目大意：

在平面上有n個點，現在要把他們拼成n/2對，拼接兩個點的代價是他們的平面距離，現在問代價總和最小是多少

輸入樣例

4 8730 9323 -3374 3929 -7890 -6727 1257 4689

輸出樣例

20366.60

數據范圍

2<=N<=20

解題思路#1：

用dfs每一次選1個數和當前數字匹配，如果當前數字選過了，就進入下一層

代碼#1：

#include<cmath> #include<cstdio> #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 (dep>n){ans=min(ans,sum);//嘗試更新答案return;}if (sum>=ans) return;//無法更新答案了if (p[dep]) dfs(dep+1,sum);//選過就直接下一層else{for (int i=dep+1;i<=n;++i)if (!p[i]){p[i]=1;dfs(dep+1,sum+dis(dep,i));//選一個和它匹配的數p[i]=0;}} } int main() {scanf("%d",&n);for (int i=1;i<=n;++i)scanf ("%lf %lf",&x[i],&y[i]);ans=9999999999.99;dfs(1,0.0);printf("%.2lf",ans); }

---

解題思路#2：

用bfs先造出一個狀壓模型，然后用模型進行狀壓DP

代碼#2：

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #define min(a,b) (a)<(b)?(a):(b) using namespace std; int n,tail=1,q[1<<21]; double x[30],y[30],f[1<<21]; int pd(int x,int y){return x&(1<<y);} 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,head=0;while(head<tail){h=q[++head];int i=n-1;for (;i>=0;--i)if (pd(h,i)) break;//找一個最高位的1for (int j=n-1;j>i;--j)//在最高位后面加1q[++tail]=h|(1<<j);} } void dp() {for (int i=1;i<=tail;++i){int s=q[i];int j=n-1;for (;j>=0;--j)if (!pd(s,j)) break;//找最高位的0for (int k=0;k<j;++k)//找一個和它相匹配的數if (!pd(s,k))f[s|(1<<j)|(1<<k)]=min(f[s|(1<<j)|(1<<k)],f[s]+dis(j,k));//狀壓DP} } int main() {scanf("%d",&n);for (int i=0;i<n;++i)scanf("%lf %lf",&x[i],&y[i]);memset(f,0x7f,sizeof(f));f[0]=0;bfs();dp();printf("%.2lf",f[(1<<n)-1]);//輸出 }

總結

以上是生活随笔為你收集整理的【状压DP】最优配对问题（jzoj 3420）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。