PAT甲级1150Travelling Salesman Problem

Posted on | | Visitors:
Words count in article: 959 字 | Reading time ≈ 4 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/1038430013544464384

题解

题目要求

  • 现在给你一些环，请你找到其中与旅行商问题答案最接近的那个环（旅行商问题的定义在此不再说明）
  • 输入
    • N：大于2，不超过200，城市的数量
    • M：无向图中边的数量，
    • M条边：每条边表示为City1 City2 Dist，其中城市索引为[1,N]，城市间距离为不超过100的正数
    • K：正整数，path的数量
    • K条path：每条path的格式为：n c1 c2 c3 … cn，其中n是path中城市的数量，ci是城市索引
  • 输出
    • 对于每条path，输出Path X: TotalDist (Description)，其中X是[1,K]，TotalDist是总距离（不存在则输出NA），Description是
      • 经过每个城市的简单环：TS simple cycle
      • 经过每个城市的环，但不是简单环：TS cycle
      • 不是经过每个城市的环：Not a TS cycle
    • 最终输出Shortest Dist(X) = TotalDist，其中X是和旅行商问题解最接近的那个环的索引，TotalDist是其距离总和。（已确保只有一个解）

解题思路

  • 距离用二维数组表示，默认值为0，为0则说明两个城市间不存在边

  • 读取每条path时，用一维数组存储某个节点被访问的次数（注意城市索引是1到N）

    在路径合法的前提下

    • TS cycle：即经过每个城市并且是一个环，即每个城市被访问的次数都大于0且首尾城市相同
    • TS simple cycle：在TS cycle的基础上，要求没有子环，只有起点城市被访问过2次，其它城市都只被访问过一次

  • 将k个path的结果存放在一维数组中

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// Problem: PAT Advanced 1150
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/1038430013544464384
// Tags: Graph TSP

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int distances[205][205]; // 各个城市之间的距离。如果为0，则说明两个城市间无边、不可直达

int main()
{
    int n, m, k;
    scanf("%d %d", &n, &m);

    int c1, c2, dist;
    for (int i = 0; i < m; i++){ // 存储各个城市之间的距离
        scanf("%d %d %d", &c1, &c2, &dist);
        distances[c1][c2] = distances[c2][c1] = dist;
    }

    int bestX, bestDist = INT_MAX;
    scanf("%d", &k);
    for(int x = 1; x <= k; x++){
        vector<int> visited(n + 1, 0);
        int numOfCities, firstCity, pathTotalDist = 0;
        bool pathIslegal = true;
        scanf("%d %d", &numOfCities, &firstCity);
        visited[firstCity] += 1; // 访问第一个城市
        c1 = firstCity; // 更新上一个城市

        for(int i = 0 ; i < numOfCities - 1; i++){
            scanf("%d", &c2); // 读取当前城市
            if (distances[c1][c2] != 0){
                visited[c2] += 1;
                pathTotalDist += distances[c1][c2]; // 计算该路径的总距离
            }
            else{ // path中两个城市不存在边
                pathIslegal = false;
            }
            c1 = c2; // 更新上一个城市
        }

        if (!pathIslegal){ // 路径非法
            printf("Path %d: NA (Not a TS cycle)\n", x);
            continue;
        }

        if (firstCity != c2){ // 在路径合法的前提下，第一个城市和最后一个城市不同，则该路径不是环
            printf("Path %d: %d (Not a TS cycle)\n", x, pathTotalDist);
            continue;
        }

        bool isTS = true;
        for (int i = 1; i < n + 1; i++){
            if (visited[i] < 1){
                isTS = false;
                break;
            }
        }
        if (!isTS){ // 该路径没有经过所有城市
            printf("Path %d: %d (Not a TS cycle)\n", x, pathTotalDist);
            continue;
        }

        bool isSimple = true;
        for (int i = 1; i < n + 1; i++){ // 已确保是环且经过所有城市，判断是否是简单环，并更新最短TS环路
            if (pathTotalDist < bestDist){
                bestX = x;
                bestDist = pathTotalDist;
            }

            if (i != firstCity && visited[i] > 1){
                isSimple = false;
            }
        }

        if (isSimple)
            printf("Path %d: %d (TS simple cycle)\n", x, pathTotalDist);
        else
            printf("Path %d: %d (TS cycle)\n", x, pathTotalDist);
    }

    printf("Shortest Dist(%d) = %d\n", bestX, bestDist);
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!