[蓝桥杯 2020 国 C] 补给

GitHub跳转原题关系图返回列表

先在“单次飞行不超过 D”的图上跑 Floyd 求任意两村庄间最短可达代价，再在这个距离矩阵上做状压 TSP。

OJ: luogu

题目 ID: P8733

难度:提高+/省选-

标签:状态压缩最短路Floyd动态规划

日期: 2026-06-21 05:17

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

直升机从总部 1 号村庄出发，要访问所有村庄后再回到总部。

单次加满油后连续飞行距离不能超过 D，但每到一个村庄都可以重新加满油。 问最小总飞行距离。

思路

先看一个小数据验证版：

cpp
#include <bits/stdc++.h>
using namespace std;

const double INF = 1e100;

int n;
double limit_d;
double x[25], y_[25];
double dis_mat[25][25];
int used[25];
double ans;

double dist(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y_[i] - y_[j];
    return sqrt(dx * dx + dy * dy);
}

void dfs_perm(int last, int cnt, double cur) {
    if (cur >= ans) {
        return;
    }
    if (cnt == n) {
        ans = min(ans, cur + dis_mat[last][1]);
        return;
    }

    for (int i = 2; i <= n; i++) {
        if (used[i] || dis_mat[last][i] >= INF / 2) {
            continue;
        }
        used[i] = 1;
        dfs_perm(i, cnt + 1, cur + dis_mat[last][i]);
        used[i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据先 Floyd，再直接枚举访问顺序。
    cin >> n >> limit_d;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y_[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            double d = dist(i, j);
            if (d <= limit_d) {
                dis_mat[i][j] = d;
            } else {
                dis_mat[i][j] = INF;
            }
        }
        dis_mat[i][i] = 0;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dis_mat[i][k] + dis_mat[k][j] < dis_mat[i][j]) {
                    dis_mat[i][j] = dis_mat[i][k] + dis_mat[k][j];
                }
            }
        }
    }

    memset(used, 0, sizeof(used));
    ans = INF;
    dfs_perm(1, 1, 0.0);

    cout.setf(ios::fixed);
    cout << setprecision(2) << ans << '\n';
    return 0;
}

暴力的思路是：

  1. 先求出任意两点之间在补给限制下的最短可达代价
  2. 再直接枚举访问顺序

正解保留第 1 步，把第 2 步改成状压 DP。

关键点在于：

  • 两村庄直线距离大于 D，并不代表永远不能到达
  • 只要可以中途经过别的村庄补油，就仍然可能可达

所以必须先建图：

  • 若两点欧氏距离 <= D，连一条边
  • 否则视为不可直接飞行

然后跑 Floyd，得到 dis_mat[i][j]：

  • 在油量限制下，从 i 到 j 的最小可达代价

做到这一步之后，原题就被转化成标准的 TSP：

  • 从 1 出发
  • 访问所有村庄
  • 回到 1

于是再做状压 DP：

  • dp[mask][u]：已经访问了 mask 中这些村庄，当前停在 u 的最小代价

DP 转移方程

在 Floyd 处理出任意两点的补给最短路后，TSP 状压转移为：

dp[mask∣(1<<v)][v]=min⁡(dp[mask∣(1<<v)][v], dp[mask][u]+dis_mat[u][v]) dp[mask \mid (1<<v)][v] =\min(dp[mask \mid (1<<v)][v],\ dp[mask][u]+dis\_mat[u][v])

最后枚举当前停点 u，再加上 dis_mat[u][1] 回到总部。

最后枚举回到总部即可。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const double INF = 1e100;

int n;
double limit_d;
double x[MAXN], y[MAXN];
double dis_mat[MAXN][MAXN];
double dp[1 << 20][20];

double dist(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return sqrt(dx * dx + dy * dy);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> limit_d;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            double d = dist(i, j);
            if (d <= limit_d) {
                dis_mat[i][j] = d;
            } else {
                dis_mat[i][j] = INF;
            }
        }
        dis_mat[i][i] = 0.0;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dis_mat[i][k] + dis_mat[k][j] < dis_mat[i][j]) {
                    dis_mat[i][j] = dis_mat[i][k] + dis_mat[k][j];
                }
            }
        }
    }

    int full = 1 << (n - 1);
    for (int mask = 0; mask < full; mask++) {
        for (int i = 1; i <= n; i++) {
            dp[mask][i] = INF;
        }
    }
    dp[0][1] = 0.0;

    for (int mask = 0; mask < full; mask++) {
        for (int u = 1; u <= n; u++) {
            if (dp[mask][u] >= INF / 2) {
                continue;
            }
            for (int v = 2; v <= n; v++) {
                if (mask & (1 << (v - 2))) {
                    continue;
                }
                if (dis_mat[u][v] >= INF / 2) {
                    continue;
                }
                int nmask = mask | (1 << (v - 2));
                dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + dis_mat[u][v]);
            }
        }
    }

    double ans = INF;
    int all = full - 1;
    for (int u = 1; u <= n; u++) {
        if (dp[all][u] >= INF / 2 || dis_mat[u][1] >= INF / 2) {
            continue;
        }
        ans = min(ans, dp[all][u] + dis_mat[u][1]);
    }

    cout.setf(ios::fixed);
    cout << setprecision(2) << ans << '\n';
    return 0;
}

复杂度

时间复杂度 O(n3+n22n)O(n^3 + n^2 2^n)，空间复杂度 O(n2+n2n)O(n^2 + n 2^n)。

总结

这题最容易错的地方，是把它误看成“直接按欧氏距离做 TSP”。 真正的关键在于先把“中途补油”折叠进最短路，再做后续的状压 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析