[PKU2677]Tour

这题是TSP的简化版：只能从左边单向走向右边，再从右边单项走回来源点，满足路径是一条哈密顿回路。

对于走两遍的要求，可以当作是两个人从左边选择两条不会有公共点的路径，单向走向右边。也就是双路DP。

一开始我的想法是f[i,j]表示A走到了i，B走到了j，那么转移的时候要么从f[i-1,j]要么从f[i,j-1]转移，为了不使两条路径相交，可以规定i>j，计算出f[i,j]后，f[j,i]=f[i,j]，方程十分简单。但是有一个问题，如果j=i-1呢？那么f[i-1,j]=f[i,i]显然就出事了！

因此要对j=i-1的情况特殊处理：寻找某个k(ki) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <cmath>
#include <iomanip>
#include <cstring>
#include <iostream>
using namespace std;

int n;
float f[51][51],x[51],y[51],ans=0x3f3f3f3f;
inline float dist(const int a,const int b) { return sqrt((x[b]-x[a])*(x[b]-x[a])+(y[b]-y[a])*(y[b]-y[a])); }
int main() {
  ios::sync_with_stdio(false);
  while (cin>>n) {
    memset(f,127,sizeof(f));
    for (int i=1;i<=n;++i) cin>>x[i]>>y[i];

    f[1][1]=0;
    for (int i=2;i<=n;++i) {
      for (int k=1;k<i;++k)
        f[i][i-1]=min(f[i][i-1],f[k][i-1]+dist(k,i));
      f[i-1][i]=f[i][i-1];
      for (int j=1;j<i-1;++j)
        f[j][i]=f[i][j]=f[i-1][j]+dist(i-1,i);
    }
    for (int i=1;i<n;++i) f[n][n]=min(f[n][n],f[n][i]+dist(i,n));
    cout<<fixed<<setprecision(2)<<f[n][n]<<endl;
  }
}

Comments