[USACO08OCT] Power Failure G

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

把已有电线当成 0 权边，把距离不超过 M 的点对当成可补的新边，在这张图上跑最短路求从 1 到 N 的最小补线长度。

OJ: luogu

题目 ID: P2914

难度:普及+/提高

标签:图论最短路

日期: 2026-06-20 04:33

目录

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

题意

有 n 根电线杆，每根都有平面坐标。
现在有 w 条现成电线还能继续使用，它们的代价视为 0。

你还可以自己新拉电线，但只能在两点直线距离不超过 M 时才能拉，而且代价就是这段直线距离。

要求让电力从 1 号点传到 n 号点，求需要补上的最小总长度。

按题目要求，最后输出：

  • 最小总长度乘 1000 后的整数部分

如果无法连通，就输出 -1。

思路

先看一个最直接的小数据做法：

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

const int MAXN = 105;
const long double INF = 1e100L;

int n, w;
long double limit_len;
long long x[MAXN], y[MAXN];
bool has_wire[MAXN][MAXN];
long double dist_arr[MAXN][MAXN];

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

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

    cin >> n >> w;
    cin >> limit_len;

    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++) {
            if (i == j) {
                dist_arr[i][j] = 0;
            }
            else {
                dist_arr[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= w; i++) {
        int u, v;
        cin >> u >> v;
        has_wire[u][v] = true;
        has_wire[v][u] = true;
        dist_arr[u][v] = 0;
        dist_arr[v][u] = 0;
    }

    // 暴力建图：所有距离不超过 M 的点对都可以补一条边。
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (has_wire[i][j]) {
                continue;
            }
            long double d = get_dist(i, j);
            if (d <= limit_len + 1e-12L) {
                dist_arr[i][j] = d;
                dist_arr[j][i] = d;
            }
        }
    }

    // 小数据直接 Floyd。
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (dist_arr[i][k] >= INF / 2) {
                continue;
            }
            for (int j = 1; j <= n; j++) {
                if (dist_arr[k][j] >= INF / 2) {
                    continue;
                }
                long double nd = dist_arr[i][k] + dist_arr[k][j];
                if (nd < dist_arr[i][j]) {
                    dist_arr[i][j] = nd;
                }
            }
        }
    }

    if (dist_arr[1][n] >= INF / 2) {
        cout << -1 << '\n';
    }
    else {
        cout << (long long) floor(dist_arr[1][n] * 1000.0L + 1e-9L) << '\n';
    }

    return 0;
}

brute.cpp 的思路其实已经很接近正解了：

  1. 先把所有原有电线记成 0 权边
  2. 再枚举所有点对
  3. 若两点距离不超过 M，就补上一条代价为欧几里得距离的边
  4. 最后 Floyd 求 1 -> n 的最短路

这个做法在小数据上完全没问题，但 n = 1000 时，Floyd 的 O(n3)O(n^3) 就太大了。

关键观察是：
题目本质上只是一个非负边权最短路。

建图方式如下：

  • 已有电线：边权是 0
  • 可以新拉且长度 <= M：边权是两点欧几里得距离
  • 其他点对：没有边

这张图可以用下面这个示意来理解：

graph LR
  A["已有电线"] -->|"0"| B["中间点"]
  B -. "sqrt(dx^2+dy^2), 且 <= M" .-> C["新拉电线"]

图里真正重要的是“同一个点对可能有两种状态”：

  1. 本来就有线，代价直接是 0
  2. 本来没线，但如果距离不超过 M，可以花这段距离去补

既然所有边权都不为负，那就直接跑 Dijkstra。

因为 n 只有 1000，这里甚至不需要链式前向星和堆优化。
直接把边权整理成一个 cost[i][j] 矩阵，再写朴素 Dijkstra 就够了：

  1. 先预处理所有 cost[i][j]
  2. cost[i][j] = 0 表示原来有线
  3. cost[i][j] = dist(i,j) 表示可以新拉
  4. cost[i][j] = INF 表示根本不能直接连接
  5. 在这张图上求 1 -> n 最短路

和代码的对应关系：

  • has_wire[i][j]：原来是否有现成电线
  • cost[i][j]：建好的边权矩阵
  • build_graph()：完成建图
  • dijkstra(1)：求从 1 出发的最短路

代码

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

const int MAXN = 1005;
const long double INF = 1e100L;

int n, w;
long double limit_len;
long long x[MAXN], y[MAXN];
bool has_wire[MAXN][MAXN];
long double cost[MAXN][MAXN];
long double dist_arr[MAXN];
bool vis[MAXN];

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

void build_graph() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                cost[i][j] = 0;
            }
            else {
                cost[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (has_wire[i][j]) {
                cost[i][j] = 0;
                cost[j][i] = 0;
                continue;
            }

            long double d = get_dist(i, j);
            if (d <= limit_len + 1e-12L) {
                cost[i][j] = d;
                cost[j][i] = d;
            }
        }
    }
}

void dijkstra(int start) {
    for (int i = 1; i <= n; i++) {
        dist_arr[i] = INF;
        vis[i] = false;
    }

    dist_arr[start] = 0;

    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (vis[j]) {
                continue;
            }
            if (u == 0 || dist_arr[j] < dist_arr[u]) {
                u = j;
            }
        }

        if (u == 0 || dist_arr[u] >= INF / 2) {
            break;
        }

        vis[u] = true;

        for (int v = 1; v <= n; v++) {
            if (vis[v] || cost[u][v] >= INF / 2) {
                continue;
            }
            long double nd = dist_arr[u] + cost[u][v];
            if (nd < dist_arr[v]) {
                dist_arr[v] = nd;
            }
        }
    }
}

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

    cin >> n >> w;
    cin >> limit_len;

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

    for (int i = 1; i <= w; i++) {
        int u, v;
        cin >> u >> v;
        has_wire[u][v] = true;
        has_wire[v][u] = true;
    }

    build_graph();
    dijkstra(1);

    if (dist_arr[n] >= INF / 2) {
        cout << -1 << '\n';
        return 0;
    }

    // 题目要求输出答案乘 1000 后的整数部分。
    cout << (long long) floor(dist_arr[n] * 1000.0L + 1e-9L) << '\n';

    return 0;
}

复杂度

预处理所有点对的边权需要：

  • O(n2)O(n^2)

朴素 Dijkstra 需要：

  • O(n2)O(n^2)

所以总时间复杂度是：

  • O(n2)O(n^2)

空间复杂度是：

  • O(n2)O(n^2)

总结

这题难点不在最短路算法本身，而在建图。

只要把题意翻译成这三种边：

  1. 原有电线：0 权
  2. 可补新线：欧几里得距离
  3. 不能补的点对：无边

后面就是一题标准的非负权单源最短路。

一图流解析

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

一图流解析