C++ 算法技巧 — 优化 (Optimization)

章节概述

优化技巧是算法竞赛中将正确解法升级为高效解法的关键手段。
涵盖图算法优化（0-1 BFS、Floyd增量更新）、数据结构优化和代码级优化。

核心原理

1. 0-1 BFS — 边权 0/1 的最短路优化

当边权仅为 0 或 1 时，用双端队列替代优先队列：

边权 0: push_front（距离不变，优先处理）
边权 1: push_back（距离 +1）

复杂度从 O(m log n) 降到 O(V+E)。

2. Floyd 增量更新

Floyd 三重循环中，k 层逐个加入中间节点。当某些节点有时间/顺序约束时，
可以按需增量加入节点进行松弛（如灾后重建问题）。

3. 最小瓶颈路问题

求 s 到 t 路径上最大边权的最小值：

方法一: 二分答案 + BFS 判定 (O(m log W))
方法二: Kruskal + 首次连通 (O(m log m))

MST 上任两点间路径的瓶颈是所有路径中最小的。

关键数据结构

F_队列_Queue — deque 实现 0-1 BFS
C_堆_Heap — priority_queue 用于常规 Dijkstra
K_并查集_UnionFind — Kruskal 路径压缩

P1346 电车

题目: N 个路口，有向轨道有默认方向（权 0）和反向（权 1）。求起点到终点的最少切换次数。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
const int INF = 1e9;
int n, a, b, dist[105];
vector<pair<int,int>> g[105];
 
int main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) dist[i] = INF;
    for (int u = 1; u <= n; u++) {
        int k, v;
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> v;
            g[u].push_back({v, j == 0 ? 0 : 1});
        }
    }
    deque<int> q;
    dist[a] = 0;
    q.push_front(a);
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        for (auto [v, w] : g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (w == 0) q.push_front(v);
                else q.push_back(v);
            }
        }
    }
    cout << (dist[b] == INF ? -1 : dist[b]) << endl;
    return 0;
}

P1119 灾后重建

题目: N 个村庄，道路在第 t_i 天后修好。Q 个询问 (x,y,t)，求第 t 天时 x 到 y 的最短路径。

#include <iostream>
using namespace std;
 
const int INF = 0x3f3f3f3f;
int n, m, t[205], f[205][205];
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            f[i][j] = (i == j ? 0 : INF);
    for (int i = 0, u, v, w; i < m; i++) {
        cin >> u >> v >> w;
        f[u][v] = f[v][u] = w;
    }
    int Q, cur = 0;
    cin >> Q;
    while (Q--) {
        int x, y, d;
        cin >> x >> y >> d;
        while (cur < n && t[cur] <= d) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (f[i][j] > f[i][cur] + f[cur][j])
                        f[i][j] = f[i][cur] + f[cur][j];
            cur++;
        }
        if (t[x] > d || t[y] > d || f[x][y] == INF)
            cout << -1 << endl;
        else
            cout << f[x][y] << endl;
    }
    return 0;
}

P1396 营救

题目: 城市拥挤度为边的权值，求从起点 s 到终点 t 的路径中，经过的最大拥挤度的最小值。

#include <iostream>
#include <algorithm>
using namespace std;
 
struct Edge { int u, v, w; } e[20005];
int fa[10005];
 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool cmp(Edge a, Edge b) { return a.w < b.w; }
 
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 0; i < m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e, e + m, cmp);
    for (int i = 0; i < m; i++) {
        fa[find(e[i].u)] = find(e[i].v);
        if (find(s) == find(t)) {
            cout << e[i].w << endl;
            return 0;
        }
    }
    return 0;
}

RootStack

探索

C++ 算法技巧 — 优化 (Optimization)

章节概述

核心原理

关键数据结构

P1346 电车

P1119 灾后重建

P1396 营救

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接