There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place. Your task is to write a program which finds such a route.
In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_1, ..., y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_{i+1}, the road y_k connects crossing points x_k and x_1. All the numbers x_1,...,x_k should be different.The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_1)+L(y_2)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible,because there is no sightseeing route in the town.
In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_1, ..., y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_{i+1}, the road y_k connects crossing points x_k and x_1. All the numbers x_1,...,x_k should be different.The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_1)+L(y_2)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible,because there is no sightseeing route in the town.
这道题本质上就是要我们在无向图中找最小环。最粗暴的做法就是枚举每一条边(u, v)，删掉之后在图中找u到v的最短路径，但是这种做法时间复杂度太高。这里我们介绍Floyd算法可以在求最短路径的同时帮我们找到图中的最小环，关于Floyd算法的介绍，请参考这篇文章，我们在这里不做过多讲解。我们知道的是Floyd算法最外层循环的k，代表了这一次找的是以{1, 2...k}为中间节点的所有最短路径，假定图中存在环，那么环上肯定存在某个编号最大的节点v，假设在环上v的两个相邻的节点为u1和u2，在我们进入k = v的循环的时候，节点u1和u2在不包含v的情况下的最短路径已经算出来了，为dist[u1][u2]因为环上最大的节点编号为v，dist[u1][u2]肯定包含了{1, 2...v - 1}的所有节点，所以dist[u1][u2] + e(v, u1) + e(v, u2)就是包含v，u1和u2，并且v为环上编号最大的点的最小环。求全局最小环，我们只需要对所有的v枚举u1和u2即可。注意这道题需要我们输出结果路径，所以我们在跑floyd的时候需要同时记录路径，我们用path[i][j]表示当前从节点i到节点j的最短路径上i的下一个节点：
- 初始化的话，对于所有相邻的节点i和j，path[i][j] = j, path[j][i] = i
- 当每次满足条件dist[i][j] > dist[i][k] + dist[k][j]的时候，代表最短路径更新了，对应的path[i][j] = path[i][k]
每次找到更小的环的时候，我们沿着path打印路径即可。总的时间复杂度O(n^3)，代码如下：
No comments:
Post a Comment