当前位置：首页 > 蓝桥杯 > 【2020蓝桥杯国赛C组】补给题解析：从Floyd到动态规划的高效解法

【2020蓝桥杯国赛C组】补给题解析：从Floyd到动态规划的高效解法

6个月前 (06-24)

一、题目解读

2020年蓝桥杯国赛C组“补给”题目要求：给定n个村庄坐标及最大补给距离D，需判断是否所有村庄均可从总部（村庄0）直接或间接到达，并计算访问所有村庄的最小路径（即旅行商问题TSP）。题目核心在于构建图模型，处理最短路径与路径规划问题，考察图论算法与动态规划的应用。

二、解题思路

1. 问题分析：首先将村庄坐标转化为图论中的节点，边权为欧几里得距离。若两点距离≤D，则边存在，否则视为不可达。

2. 最短路径计算：采用Floyd-Warshall算法计算任意两点间的最短路径，构建完整距离矩阵。

3. 路径规划优化：转化为TSP问题，使用动态规划求解。状态定义为已访问村庄的集合（二进制掩码）与当前位置，通过状态转移方程逐步扩展路径。

4. 可行性判断：若总部与任一村庄不可达，直接输出-1；否则计算最小路径。

三、解题步骤

1. 输入与初始化：读取村庄数量n和最大距离D，存储村庄坐标到vector<pair<int, int>>。

2. 构建邻接矩阵：计算所有村庄间的欧几里得距离，若距离≤D则赋值，否则设为INF（表示不可达）。

3. Floyd-Warshall算法：三层循环更新任意两点间的最短路径，利用传递性优化距离。

4. 动态规划求解TSP：

状态定义：dp[mask][i]表示已访问村庄集合为mask，当前位于村庄i的最小路径。

边界条件：dp[1][0] = 0（仅访问总部）。

状态转移：枚举当前村庄last和下一村庄next，若next在mask中且路径可达，更新dp[mask | (1 << next)][next] = min(dp[mask][last] + dist[last][next])。

5. 输出结果：检查所有村庄是否可达，并返回最小路径或-1。

四、代码与注释

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

const double INF = 1e18;

// 计算两点之间的欧几里得距离
double calculateDistance(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
    int n, D;
    cin >> n >> D;
    
    vector<pair<int, int>> villages(n); // 存储村庄坐标
    for (int i = 0; i < n; ++i) {
        cin >> villages[i].first >> villages[i].second;
    }
    
    // 构建邻接矩阵，计算所有村庄之间的距离
    vector<vector<double>> dist(n, vector<double>(n, INF));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            double d = calculateDistance(villages[i].first, villages[i].second, 
                                       villages[j].first, villages[j].second);
            // 如果距离超过D，则不能直接到达
            dist[i][j] = (d <= D)? d : INF;
        }
    }
    
    // Floyd-Warshall算法计算所有点对之间的最短路径
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // 检查是否所有村庄都可到达
    for (int i = 1; i < n; ++i) {
        if (dist[0][i] == INF || dist[i][0] == INF) {
            cout << "-1" << endl;
            return 0;
        }
    }
    
    // 旅行商问题(TSP)的动态规划解法
    vector<vector<double>> dp(1 << n, vector<double>(n, INF));
    dp[1][0] = 0; // 初始状态：只访问了总部(村庄0)
    
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int last = 0; last < n; ++last) {
            if (!(mask & (1 << last))) continue;
            if (dp[mask][last] == INF) continue;
            
            for (int next = 0; next < n; ++next) {
                if (mask & (1 << next)) {
                    dp[mask | (1 << next)][next] = 
                        min(dp[mask | (1 << next)][next], dp[mask][last] + dist[last][next]);
                }
            }
        }
    }
    
    // 输出最小路径
    cout << fixed << setprecision(2) << dp[(1 << n) - 1][0] << endl;
    return 0;
}