双调欧几里得旅行商问题解法 (POJ 2677)-白红宇

双调欧几里得旅行商问题解法 (POJ 2677)

阅读量：5091 次

发布时间：2019-06-13

本文共 2522 字，大约阅读时间需要 8 分钟。

对于这个解法，网上题解一大堆。不过觉得还是算导官方给的解答好些，简洁又清楚。。。

大概总结一下(不是翻译)=.=

首先是排序。

然后确定状态 f[i][j] (i >= j, i == j表示的只有n这个点) 表示从i到1严格从右往左走然后再从1严格从左往右走到j 这样两条路径的最小值，当然[1, max(i, j)]区间上所有的点都是被访问过得。

存在两种状态 :

1: j < i - 1;

dp[i][j] = dp[i-1][j] + Dis(i, i - 1);

2: j == i - 1;

dp[i][j] = min{dp[i][j], dp[j][k] + Dis(k, i)}　　//这个dp[j][k]本来应该是dp[k][j]的，但是由于dp[x][y] = dp[y][x]所以用dp[j][k]表示更方便，因为dp[i][j]满足i > j, dp[j][k]也满足j > k。

POJ 2677&&HDU 2224代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #include 
                   
                    16 17 #define CL(arr, val) memset(arr, val, sizeof(arr))18 #define REP(i, n) for((i) = 0; (i) < (n); ++(i))19 #define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i))20 #define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i))21 #define L(x) (x) << 122 #define R(x) (x) << 1 | 123 #define MID(l, r) (l + r) >> 124 #define Min(x, y) x < y ? x : y25 #define Max(x, y) x < y ? y : x26 #define E(x) (1 << (x))27 #define iabs(x) (x) < 0 ? -(x) : (x)28 #define OUT(x) printf("%I64d\n", x)29 #define lowbit(x) (x)&(-x)30 #define Read() freopen("data.in", "r", stdin)31 #define Write() fropen("data.out", "w", stdout);32 33 const int eps = 1e-8;34 typedef long long LL;35 const double inf = 1e15;36 37 using namespace std;38 39 const int N = 1024;40 41 double f[N][N];42 double dis[N][N];43 44 struct node {45 int x;46 int y;47 bool operator < (const node cmp) const {48 return x == cmp.x ? y < cmp.y : x < cmp.x;49 }50 }p[N];51 52 double Dis(int i, int j) {53 return sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x)*1. + (p[i].y - p[j].y)*(p[i].y - p[j].y)*1.);54 }55 56 int main() {57 // Read();58 int n, i, j, k;59 double ans;60 while(~scanf("%d", &n)) {61 for(i = 1; i <= n; ++i) scanf("%d%d", &p[i].x, &p[i].y);62 sort(p + 1, p + n + 1);63 for(i = 1; i <= n; ++i) {64 for(j = 1; j <= i; ++j) {65 dis[i][j] = dis[j][i] = Dis(i, j);66 }67 }68 f[2][1] = dis[2][1];69 //i >= j70 for(i = 3; i <= n; ++i) {71 //j < i - 172 for(j = 1; j < i - 1; ++j) f[i][j] = f[i-1][j] + dis[i-1][i];73 //j == i - 174 j = i - 1;75 f[i][j] = inf;76 for(k = 1; k < j; ++k) {77 f[i][j] = min(f[i][j], f[j][k] + dis[k][i]); //note: f[x][y] = f[y][x]78 }79 }80 81 if(n == 2) ans = f[2][1];82 else ans = f[n][n-1] + dis[n][n-1];83 printf("%.2f\n", ans);84 }85 return 0;86 }

转载于:https://www.cnblogs.com/vongang/archive/2012/09/15/2686576.html

你可能感兴趣的文章