ECNA 2018 I Tours de sales Force

by ·0评论

题意：有n个人，n<=50且为偶数。原先每个人有一个配送任务，要求在平面上不重复得经过p个点(p<=8)，而且总路程最短。现在因公司经营不善裁掉后一半的人，前面每个人接管一个后半部分的人的任务。问之裁之前和裁之后的最短总路程。

对于前一个问题，这是一个典型的旅行商问题。使用经典的状压dp可在O(p^2 * 2^p)求解出最短的总路程：设dp[mask][j]为走完mask位上为1位置，且最后一步为j点的最短路线，转移时枚举下一个点即可。

对于后一个问题，我们需要求出前半部分和后半部分两两组合的最短路程，然后取一个最小的二分图带权匹配即可。其中复杂度的瓶颈在于前面枚举两两组合的tsp，需要卡一卡常，dp时应尽量避免无效状态。
时间复杂度O(n^2 * p^2 * 2^p)。

其中计算tsp的过程也可以采用一些非完美算法来降低时间复杂度，但没有必要。

  1. /*
  2. Author: fffasttime
  3. Date: 2019/07/23 21:20
  4.  */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. #define inc(i,n) for (int i=0;i<n;i++)
  9. const int N=100010;
  10. typedef double db;
  11.  
  12. struct vec{
  13.     int x,y;
  14. };
  15. db dis(vec &a, vec &b){
  16.     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  17. }
  18.  
  19. db di[16][16], dp[1<<16][16];
  20. db tsp(int n){ //tsp circle
  21.     if (n==1) return 0;
  22.     inc(i,1<<(n-1)) inc(j,n-1) dp[i][j]=1e10; 
  23.     inc(i,n-1) dp[1<<i][i]=di[i][n-1]; //force set start point at n-1
  24.     inc(i,1<<n-1){
  25.         inc(j,n-1) {
  26.             if ((i>>j&1)==0)
  27.             inc(k,n-1) if (i>>k&1) 
  28.                 dp[i|1<<j][j]=min(dp[i|1<<j][j],dp[i][k]+di[j][k]);
  29.         }
  30.     }
  31.     db ans=1e10;
  32.     inc(i,n-1) ans=min(ans, dp[(1<<n-1)-1][i]+di[i][n-1]);
  33.     return ans;
  34. }
  35. vector<vec> p[60];
  36.  
  37. db d[30][30],cx[30],cy[30],cc[30];
  38. int to[30], ux[30], uy[30];
  39. int m;
  40.  
  41. bool find(int u){
  42.     ux[u]=1;
  43.     for (int i=1;i<=m;i++){
  44.         if (uy[i]) continue;
  45.         if (cx[u]+cy[i]==d[u][i]){
  46.             uy[i]=1;
  47.             if (!to[i]||find(to[i])) {
  48.                 to[i]=u;
  49.                 return 1;
  50.             }
  51.         }
  52.         else cc[i]=min(cc[i],cx[u]+cy[i]-d[u][i]);
  53.     }
  54.     return 0;
  55. }
  56. db km(){
  57.     for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) 
  58.         cx[i]=max(cx[i],d[i][j]);
  59.     for (int i=1;i<=m;i++){
  60.         memset(ux,0,sizeof ux); memset(uy,0,sizeof uy);
  61.         inc(i,30) cc[i]=1e10;
  62.         if (find(i)) continue;
  63.         db ms; int u;
  64.         while (1){
  65.             ms=1e10;
  66.             for (int j=1;j<=m;j++) if (!uy[j]) ms=min(ms,cc[j]);
  67.             for (int j=1;j<=m;j++) if (ux[j]) cx[j]-=ms;
  68.             for (int j=1;j<=m;j++) if (uy[j]) cy[j]+=ms;
  69.                 else cc[j]-=ms,cc[j]==0?u=j:0;
  70.             if (!to[u]) break;
  71.             uy[u]=ux[to[u]]=1;
  72.             u=to[u];
  73.             for (int j=1;j<=m;j++) cc[j]=min(cc[j],cx[u]+cy[j]-d[u][j]);
  74.         }
  75.         memset(ux,0,sizeof ux); memset(uy,0,sizeof uy);
  76.         find(i);
  77.     }
  78.     db ans=0;
  79.     for (int i=1;i<=m;i++) ans+=d[to[i]][i];
  80.     return ans;
  81. }
  82.  
  83. int main(){
  84.     int n,_,x,y; cin>>n;
  85.     db dis0=0;
  86.     inc(i,n){
  87.         cin>>_;
  88.         inc(j,_) cin>>x>>y,p[i].push_back({x,y});
  89.         inc(j,_) inc(k,_) di[j][k]=dis(p[i][j],p[i][k]);
  90.         dis0+=tsp(_); //cout<<tsp(_)<<'\n';
  91.     }
  92.     inc(i,n/2) inc(j,n/2){
  93.         vector<vec> tp(p[i]); 
  94.         tp.insert(tp.end(),p[j+n/2].begin(),p[j+n/2].end());
  95.         inc(k,tp.size()) inc(l,tp.size()) di[k][l]=dis(tp[k],tp[l]);
  96.         db ret=tsp(tp.size());
  97.         d[i+1][j+1]=1e6-ret;
  98.     }
  99.     m=n/2;
  100.     db mat=1e6*m-km();
  101.     printf("%.6lf %.6lf\n",dis0,mat);
  102.     return 0;
  103. }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注