Tour UVA - 1347 旅行 DAG

题目链接

给定平面上n（n≤1000）个点的坐标（按照x递增的顺序给出。各点x坐标不同，且均为正整数），你的任务是设计一条路线，从最左边的点出发，走到最右边的点后再返回，要求除了最左点和最右点之外每个点恰好经过一次，且路径总长度最短。两点间的长度为它们的欧几里德距离，如图9-4所示。

【分析】
       “从左到右再回来”不太方便思考，可以改成：两个人同时从最左点出发，沿着两条不同的路径走，最后都走到最右点，且除了起点和终点外其余每个点恰好被一个人经过。这样，就可以用d(i,j)表示第一个人走到i，第二个人走到j，还需要走多长的距离。状态如何转移呢？仔细思考后会发现：好像很难保证两个人不会走到相同的点。例如，计算状态d(i,j)时，能不能让i走到i＋1呢？不知道，因为从状态里看不出来i＋1有没有被j走过。换句话说，状态定义得不好，导致转移困难。

       下面修改一下：d(i,j)表示1～max(i,j)全部走过，且两个人的当前位置分别是i和j，还需要走多长的距离。不难发现d(i,j)=d(j,i)，因此从现在开始规定在状态中i＞j。这样，不管是哪个人，下一步只能走到i＋ 1 , i＋2,…这些点。可是，如果走到i＋2，情况变成了“1～i和i＋2，但是i＋1没走过”，无法表示成状态！怎么办？禁止这样的决策！也就是说，只允许其中一个人走到i＋1，而不能走到i＋ 2 , i＋3,…。换句话说，状态d(i,j)只能转移到d(i＋1,j)和d(i＋1,i)。

       可是这样做产生了一个问题：上述“霸道”的规定是否可能导致漏解呢？不会。因为如果第一个人直接走到了i＋2，那么它再也无法走到i＋1了，只能靠第二个人走到i＋1。既然如此，现在就让第二个人走到i＋1，并不会丢失解。边界是d(n－1,j)=dist(n－1,n)＋dist(j,n)，其中dist(a,b)表示点a和b之间的距离。因为根据定义，所有点都走过了，两个人只需直接走到终点。所求结果是dist(1,2)＋d(2,1)，因为第一步一定是某个人走到了第二个点，根据定义，这就是d(2,1)。

状态转移方程：

d(i,j)=min(d(i+1,j)+dist(i,i+1),d(i+1,i)+dist(j,i+1));

第二项表示为d(i+1,i)是因为已经规定i>j，又根据d(i,j)的定义易知有d(i,j)=d(j,i)，因此d(i,i+1)可写为d(i+1,i)。

本题的状态数有O(N^2)个，每次状态的决策只有2个，因此时间复杂度为O(N^2)。

#include 
#include 
#include 
using namespace std;
const int N = 55;
double x[N], y[N], d[N][N], dist[N][N];
int main(int argc, char** argv) {int n;while( ~scanf("%d",&n)){for(int i = 1; i <= n; i++) scanf("%lf%lf",&x[i],&y[i]);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dist[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));for(int i = n-1; i >=2 ; i--)for(int j = 1; j < i; j++)if(i == n-1) d[i][j] = dist[i][n] + dist[j][n]; // 边界else d[i][j] = min(dist[i][i+1] + d[i+1][j], dist[j][i+1] + d[i+1][i]);	printf("%.2lf\n", dist[1][2] + d[2][1]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！