购物网站建设模板下载,建设三轮摩托车官网,设计网站下载,购物网站开发【PAT甲级题解记录】1150 Travelling Salesman Problem (25 分)
前言 Problem#xff1a;1150 Travelling Salesman Problem (25 分) Tags#xff1a;模拟 图的遍历 旅行商问题 Difficulty#xff1a;剧情模式 想流点汗 想流点血 死而无憾 Address#xff1a;1150 Travell…【PAT甲级题解记录】1150 Travelling Salesman Problem (25 分)
前言 Problem1150 Travelling Salesman Problem (25 分) Tags模拟 图的遍历 旅行商问题 Difficulty剧情模式 想流点汗 想流点血 死而无憾 Address1150 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:
参考代码
#includeiostream
#includecstdio
#includevector
#includesetusing namespace std;
int N; // the number of cities
int M; // the number of edges in an undirected graph
vectorvectorint 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;vectorint 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; // 判断重复是否简单环setint 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;
}
