【PAT甲级题解记录】1150 Travelling Salesman Problem (25 分)

前言

Problem：1150 Travelling Salesman Problem (25 分)

Tags：模拟 图的遍历 旅行商问题

Difficulty：剧情模式 想流点汗 想流点血 死而无憾

Address：1150 Travelling Salesman Problem (25 分)

问题描述

给定一个图和一些路径，求这些路径是否为旅行商环路、简单旅行商环路或者非旅行商环路。

• TS simple cycle if it is a simple cycle that visits every city;
• TS cycle if it is a cycle that visits every city, but not a simple cycle;
• Not a TS cycle if it is NOT a cycle that visits every city.

解题思路

只要会存储图，模拟一下就可以了。

唯一的难点是三种路径类型的判断上并没有那么轻松，甚至读题也有点麻烦，还是有点烦的，不过样例能过基本上就没问题了。

建议在遍历路径判断前像这样打个草稿，这种题思路一定要严谨清晰。

// Not a TS cycle if it is NOT a cycle that visits every city.
if(不连通 or 首尾不通 or 不包含全部) // 其中不连通输出NA// TS cycle if it is a cycle that visits every city, but not a simple cycle;
else if(有重复): // TS simple cycle if it is a simple cycle that visits every city;
else: 

参考代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>using namespace std;
int N;  // the number of cities
int M;  // the number of edges in an undirected graph
vector<vector<int>> edges;  // 邻接矩阵
void init() {cin >> N >> M;// 初始化 edges (-1)edges.resize(N + 1);for (int i = 1; i <= N; ++i) {edges[i].resize(N + 1, -1);}// 输入 edgesfor (int i = 0; i < M; ++i) {int c1, c2, d;cin >> c1 >> c2 >> d;edges[c1][c2] = d;edges[c2][c1] = d;}}void solve() {int K;cin >> K;int min_dist = 0x3f3f3f3f;int min_index = -1;for (int k = 1; k <= K; ++k) {int n;cin >> n;vector<int> path(n);for (int i = 0; i < n; i++) {cin >> path[i];}// checkint dist = 0;bool is_conn = true; // 判断路径通不通bool is_all = true; // 判断是否 visit every citybool is_simple = true; // 判断重复（是否简单环）set<int> visited; // 访问计数，用来判断重复visited.insert(path[0]);for (int i = 1; i < n; ++i) {if (edges[path[i - 1]][path[i]] == -1) {is_conn = false;}if (i != n - 1 && visited.count(path[i])) {  // 注意末尾不判断，末尾是用来构成环的is_simple = false;}dist += edges[path[i - 1]][path[i]];visited.insert(path[i]);}if (visited.size() != N) {is_all = false;}if (!is_conn) {printf("Path %d: NA (Not a TS cycle)\n", k);} else if (!is_all || path[0] != path[n - 1]) {printf("Path %d: %d (Not a TS cycle)\n", k, dist);} else if (!is_simple) {printf("Path %d: %d (TS cycle)\n", k, dist);if (dist < min_dist) {min_dist = dist;min_index = k;}} else {printf("Path %d: %d (TS simple cycle)\n", k, dist);if (dist < min_dist) {min_dist = dist;min_index = k;}}}printf("Shortest Dist(%d) = %d\n", min_index, min_dist);
}void solution_1150() {init();solve();
}
int main() {solution_1150();return 0;
}