题目描述

我们需要确定Georgia和Bob访问所有珠宝房间并返回起点所需的最小距离，以及达到这一最小距离的有效访问顺序的数量。问题基于一个树结构，其中所有珠宝房间都是叶子节点。

方法思路

1. 问题分析： • 这个问题是树结构上的旅行商问题（TSP）的一个变种。

   • 树结构确保每个珠宝房间（叶子节点）通过唯一的路径连接，所有内部节点至少有两个子节点。

2. 关键点： • 访问所有叶子节点并返回起点的最小距离是树中所有边权之和的两倍。

   • 有效访问顺序的数量由树中每个内部节点的子节点数量的阶乘乘积决定，模2005。

3. 算法步骤： • 计算最小距离：最小距离由树结构中所有叶子节点之间的距离总和调整得出。

   • 确定有效顺序：有效顺序的数量是每个内部节点的子节点数量的阶乘乘积，模2005。

解决代码

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

int fact[31];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= 30; ++i) {
        fact[i] = (fact[i-1] * i) % 2005;
    }
}

int main() {
    precompute();
    int n;
    while (cin >> n && n != 0) {
        vector<vector<int>> d(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> d[i][j];
            }
        }
        
        // 计算所有节点对的距离总和
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                sum += d[i][j];
            }
        }
        int total_distance = 2 * sum / (n-1);
        
        // 重建父节点关系
        vector<int> parent(n, -1);
        for (int i = 1; i < n; ++i) {
            int max_d = -1;
            int p = 0;
            for (int j = 0; j < n; ++j) {
                if (j == i) continue;
                if (d[0][j] + d[j][i] == d[0][i]) {
                    if (d[0][j] > max_d) {
                        max_d = d[0][j];
                        p = j;
                    }
                }
            }
            parent[i] = p;
        }
        
        // 计算每个节点的子节点数量
        vector<int> child_count(n, 0);
        for (int i = 1; i < n; ++i) {
            child_count[parent[i]]++;
        }
        
        // 计算结果
        int res = 1;
        for (int cnt : child_count) {
            if (cnt > 0) {
                res = (res * fact[cnt]) % 2005;
            }
        }
        
        cout << total_distance << " " << res << endl;
    }
    return 0;
}

代码解释

1. 预计算阶乘：预先计算阶乘模2005的值，以便高效计算有效排列数。
2. 读取输入：读取并存储输入的矩阵。
3. 计算距离总和：计算所有叶子节点之间的距离总和。
4. 确定最小距离：根据树的性质，最小距离为距离总和的两倍除以节点数减一。
5. 重建树结构：利用距离矩阵确定每个节点的父节点，重建树的结构。
6. 统计子节点数：统计每个内部节点的子节点数量。
7. 计算有效顺序数：利用子节点数量的阶乘乘积，模2005，计算有效访问顺序的数量。

这种方法高效地利用了树结构的特性，确保在节点数最多为30的情况下，仍能在合理时间内解决问题。