当前位置：首页 > news >正文

【代码随想录day59】【C++复健】 47. 参加科学大会（dijkstra（堆优化版）精讲）；94. 城市间货物运输 I

news 来源：原创 2025/6/21 6:48:58

前几天有些事情耽搁了，不过好在图论我完全不会，所以偷看代码思路也没有任何的心理负担，做起来反而相对独立思考更快一点点。

47. 参加科学大会（dijkstra（堆优化版）精讲）

本来一开始以为这个堆优化版相对于朴素版就类似于kruskal算法之于prim算法，定睛一看才发现并非如此，区别还是有很多的。

因为是时隔好几天回来写代码，有一种恍若隔世的感觉，甚至有点忘了kruskal/prim以及dijkstra算法都是针对什么问题的，所以就问了一下GPT，没想到还是挺有收获的：

1. 计算目标的不同：

Prim 和 Kruskal：

目标：构造一棵 最小生成树 (Minimum Spanning Tree, MST)。
- 目的在于找到一个无向图中连接所有节点的总权重最小的树。
- 生成树不关注特定的起点或终点，而是全图的一种全局性质。
- MST 确保所有节点都被连接且总权重最小，但并不保证某个节点到另一个节点的最短路径。

Dijkstra：

目标：计算一个特定起点到图中所有其他节点的 最短路径。
- 主要用于单源最短路径问题。
- 仅关注从起点到终点的最短权重和路径，而不会覆盖所有节点。

2. 输入图类型的不同：

特性	Prim/Kruskal	Dijkstra
图类型	无向图	有向图或无向图均可
边权值特性	权值非负（负权值不影响）	权值必须非负

3. 使用的算法思想：

Prim：

基于 贪心法 构造 MST。
从某个节点出发，每次选择权值最小的边扩展树，直到包含所有节点。
支持动态增加节点，并使用优先队列进行优化（时间复杂度可以为 O((n+m)log⁡n)O((n + m) \log n)O((n+m)logn)）。

Kruskal：

基于 贪心法 和 并查集，构造 MST。
将图中的所有边按权值排序，然后从最小权值开始加入树中，同时避免形成环。
更适合处理稀疏图，时间复杂度为 O(mlog⁡m)O(m \log m)O(mlogm)，其中 mmm 是边的数量。

Dijkstra：

基于 贪心法 和优先队列。
从起点出发，每次选择当前路径最短的节点，更新邻接节点的最短距离，直到所有节点的最短距离确定。
时间复杂度为 O((n+m)log⁡n)O((n + m) \log n)O((n+m)logn)。

4. 结果的不同：

Prim 和 Kruskal：

输出是一个包含 n−1n-1n−1 条边的 最小生成树。
生成树覆盖了所有节点，但并不提供任何节点对之间的最短路径信息。
最小生成树 ≠ 最短路径树（MST 不适合直接用于单源最短路径问题）。

Dijkstra：

输出是从起点到其他节点的最短路径。
生成的树是以起点为根的 最短路径树。
最短路径树并不一定是最小生成树，因为两者优化目标不同。

简单来说，kruskal/prim的最终目的是要找一个最小生成树把所有节点都连起来，而dijkstra单纯只是想知道从a到b的最短路径是什么。

那次是很容易想到一个新的问题：最小生成树当中两个节点之间的距离是最短路径吗？

并不是。比如最小生成树当中有可能是a-d，c-d，那我从a到c就是a-d加上c-d的权值，那假设我有一个直接连接a-c的边且权值比a-d加上c-d的权值要小，那最小生成树里的这个权值就不是最短路径。举个例子：

       (2)         (4)A ------- B -------- C\       /(3)\   /(3)D/    \(6)/      \(1)E -------- F(5)

最终最小生成树是这样的：

       (2)         (4)A ------- B -------- C\(3)\D ----- F(1)\(5)\E

按树去算就会得到6而不是4（ac的边权值）。

好了，接下来就来边看解析边抄代码：

1 专门定义了一个类来比较小顶堆里面元素的大小，不知道如果单纯用一个bool类型的函数能不能行？

本来以为是可以的，因为sort函数就可以传一个简单函数，但实际一跑发现报错了，方知这样是不行的，原因我们还是看GPT的说法：

1. `std::sort` 与 `priority_queue` 的实现差异

std::sort： std::sort 是一个算法，通常是实现为一个模板函数。它接受一个比较器（可以是普通函数、函数指针、函数对象、或者 lambda 表达式），并且这个比较器是传递给算法的一个参数。在排序的过程中，std::sort 会根据比较器对元素进行比较排序。

std::sort 内部通常是通过循环遍历容器来进行排序，比较操作只是其中的一个环节。传递给 std::sort 的比较器（无论是函数指针还是函数对象）会被调用来决定两个元素的顺序。这种设计允许函数指针或者函数对象作为比较器，因为它们是可以被直接调用的。
priority_queue： std::priority_queue 是一个容器适配器，它通过底层的容器（通常是 vector 或 deque）来维护元素，并且提供一个优先级的队列结构。其最大特点是它内部会自动维护一个堆结构（通常是最大堆或者最小堆），并且它会根据优先级进行自动排序。

由于 priority_queue 是一个容器适配器，它并不直接进行排序，而是通过对元素进行插入、删除的操作来维护堆结构。它需要一个比较器来定义堆的排序规则。在这种情况下，priority_queue 需要一个 可调用的对象（例如函数对象、函数指针、lambda 表达式）作为比较器，而不能直接使用普通的函数。

当你使用普通函数时，priority_queue 无法直接使用它，因为 C++ 中的普通函数并不直接满足可以作为比较器使用的要求。priority_queue 需要一个函数对象，而函数对象必须满足 operator() 可以被调用。

2. 普通函数与函数对象的区别

普通函数： 普通函数（例如 bool cmp(pair<int, int> a, pair<int, int>)）不是一个类或对象，不能像对象那样通过 () 调用。因此，不能直接作为 priority_queue 的比较器。priority_queue 期望比较器是一个具有调用操作符 operator() 的对象。
函数对象： 函数对象（或可调用对象）是一个类的实例，并且这个类实现了 operator()。这使得函数对象可以像函数一样被调用，从而可以作为比较器传递给 priority_queue。例如：
```
struct Compare {bool operator()(const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;  // 最小堆的比较规则}
};
```
Lambda 表达式： Lambda 表达式本质上也是一个匿名的函数对象，它也实现了 operator()。因此，你可以将 lambda 表达式直接传递给 priority_queue，像传递函数对象一样：
```
priority_queue<pair<int, int>, vector<pair<int, int>>, function<bool(pair<int, int>, pair<int, int>)>> pq([](pair<int, int> a, pair<int, int> b) {return a.second > b.second;  // 最小堆});
```

3. `std::sort` 和 `priority_queue` 的设计目的不同

std::sort：是一个排序算法，处理的是一次性对所有元素进行排序。它只是对容器中的元素进行排序，并不需要维持元素的顺序或者结构，因此它可以直接接收一个普通函数或者其他任何可调用对象作为比较器。
priority_queue：是一个数据结构，旨在维护一个元素的优先级队列，它会根据优先级的顺序来自动调整元素的顺序。因此，priority_queue 必须保持一个堆结构，并且它在每次插入或弹出元素时都会重新调整堆的顺序。为了实现这一点，它要求传入一个比较器，来定义元素的优先级。

4. 函数指针和函数对象的不同

std::sort 支持函数指针，因为它不需要持续保持比较操作符，排序完成后就不再需要调用比较器了。
priority_queue 需要的是一个 可调用对象（通常是一个函数对象），它持续地在队列内部进行元素比较。因此，直接使用普通函数会导致不兼容的情况。

结论

std::sort 可以接受普通函数作为比较器，是因为它只是作为一个排序算法，传入的比较器是一次性使用的，不需要持续地调用。
priority_queue 需要一个 函数对象 或其他可调用对象（比如 lambda），因为它需要一个在每次操作（插入、弹出）时都可以调用的比较器。

但我看到这里还是没看太懂，为什么它那样写就是一个可调用对象呢？我继续追问，得到了这样的答案：

1. 普通函数 vs 可调用对象

普通函数：普通函数是一个具有特定名称和签名的函数。在 C++ 中，普通函数只是一个代码块，它并不具备像对象那样的状态，也没有成员函数，因此不能像对象一样直接调用。你只能通过名称来调用它，并且它不能像对象一样持有数据或状态。

比如：
```
bool cmp(pair<int, int> a, pair<int, int> b) {return a.second > b.second;  // 比较函数
}
```
这个函数 可以作为参数传递给 std::sort 等算法，但它不能直接作为一个对象一样被调用。你通常需要通过函数指针来传递它。
可调用对象（Callable Object）：可调用对象是一个实现了 operator() 的对象（通常是一个类或结构体）。这样，它的实例就变成了一个可以像函数一样被调用的对象。换句话说， 只要某个类或者结构体重载了 operator()，它就变成了一个可调用对象。

举个例子，像你提到的 Compare：
```
bool cmp(pair<int, int> a, pair<int, int> b) {return a.second > b.second;  // 比较函数
}
```
在这个例子中，Compare 是一个结构体，它定义了 operator()，使得它的对象变得 可调用。这意味着你可以通过 () 运算符直接调用 Compare 类的对象，像调用普通函数一样。

例如：
```
struct Compare {bool operator()(const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;  // 比较规则}
};
```
在这种情况下，Compare 结构体的对象 cmp 充当了一个 可调用对象，它的 operator() 被用作比较操作。

2. 为什么 `Compare` 是可调用对象，而普通函数不是？

关键点在于 operator()，这是 C++ 中让对象变得可调用的机制。普通函数是没有 operator() 的，因此它们不能像对象一样被调用，只能通过函数指针传递给其他函数或容器。

operator() 的作用：
当你在类或结构体中定义了 operator()，你实际上让这个类或结构体的对象变得可以像函数一样调用。这样，你就能通过 实例化类/结构体对象并调用该对象的 operator() 来实现功能。operator() 可以持有状态或数据，因此它比普通函数更加灵活。

2 定义了一个edge类型，还有构造函数，构造函数是为了后写 vector[left].push_back(Edge(right, val));的时候往里面直接插入edge类型的元素，但是为什么后面在定义有限对了的时候写的是priority_queue<pair<int, int> 而不是 priority_queue<Edge呢？

在定义上来说，这个优先队列里面存的是从源点出发到当前节点的距离，而并不是带权值的边，在定义上是不太对头的，但如果真的写成edge，然后里面存从源点出发到当前节点的距离，语法上也是不会报错的，并且也能得到正确答案，但可读性就很差了。

3 我会觉得pirorty_queue<pair<int, int>, vector<pair<int, int>, cmp> pq;这句话里面，第二个参数其实已经完全包含了第一个参数里面的信息，所以比较好奇C++为什么是这样设置的，但问了GPT半天它也没讲太明白，我就不放上来了，就当是c++的一个不太合理之处吧。

4 卡哥代码里面有这样一段：

        for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge// cur指向的节点edge.to，这条边的权值为 edge.valif (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDistminDist[edge.to] = minDist[cur.first] + edge.val;pq.push(pair<int, int>(edge.to, minDist[edge.to]));}}

当时看完了感觉这样插入可能会产生很多无效的距离被插入的情况，因为后续当mindist更新的时候，前面的更长的那个距离已经被push进到最小堆里面去了。不过这也是没办法的事情，不这样写的话甚至不知道怎么写插入的代码。而且只要再加上这样一句：

        if(visited[cur.first]){continue;}

就能把那些并非最优的情况（已经在前面已经有更小的距离出现，并且已经访问过）滤掉（一开始还在好奇为什么写这么一句，现在懂了）。

还有若干问题，比如初始化边的时候应该是i < m才对，结果写成了i < n；还有就是下标从1开始，结果我又初始化了0号位，导致产生问题...

#include<iostream>
#include<vector>
#include<list>
#include <queue>
#include <climits>
using namespace std;struct Edge{int to, val;Edge(int t, int v):to(t), val(v){}
};struct Compare {bool operator()(const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;}
};int main(){int n, m;cin >> n >> m;vector<list<Edge>> grid(n+1);for(int i=0; i<m; i++){int left, right, val;cin >> left >> right >> val;grid[left].push_back(Edge(right, val));}vector<int> mindist(n+1, INT_MAX);vector<bool> visited(n+1);priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;pq.push({1, 0});mindist[1] = 0;while(!pq.empty()){pair<int, int> cur = pq.top();pq.pop();if(visited[cur.first]){continue;}visited[cur.first] = true;for(Edge edge: grid[cur.first]){if(!visited[edge.to] && mindist[cur.first] + edge.val < mindist[edge.to]){mindist[edge.to] = mindist[cur.first] + edge.val;pq.push(pair<int, int>(edge.to, mindist[edge.to]));}}}if(mindist[n] == INT_MAX){cout << -1;}else{cout << mindist[n];}
}

94. 城市间货物运输 I

老样子边看解析边抄，看了之后发现插入元素用的grid.push_back({p1, p2, val});。这个和 grid[p1][p2] = val;一样吗？完全不一样，虽然都是两层vector，一个存的是点的格子，另一个是所有边的集合。

#include<iostream>
#include<vector>
#include<list>
#include<climits>
using namespace std;int main(){int n, m;cin >> n >> m;vector<vector<int>> grid;for(int i=0; i<m; i++){int left, right, weight;cin >> left >> right >> weight;grid.push_back({left, right, weight});}int start = 1;int end = n;vector<int> mindist(n+1, INT_MAX);mindist[start] = 0;for(int i=1; i<n; i++){for(vector<int>& side: grid){int left = side[0];int right = side[1];int val = side[2];if(mindist[left] != INT_MAX && mindist[left] + val < mindist[right]){mindist[right] = mindist[left] + val;}}}if (mindist[end] == INT_MAX) {cout << "unconnected";}else{cout << mindist[end];}
}

总的来说本题并不像上一题一样细节很多而且用到了很多不熟悉的东西，本题思路很简单，就是两个for循环挨个节点去遍历，总共搞n-1次，自己写估计也能做，但是有点被上一题搞怕了，还以为这个题会更难，直接就抄了。

47. 参加科学大会（dijkstra（堆优化版）精讲 ）

1. 计算目标的不同：

Prim 和 Kruskal：

Dijkstra：

2. 输入图类型的不同：

3. 使用的算法思想：

Prim：

Kruskal：

Dijkstra：

4. 结果的不同：

Prim 和 Kruskal：

Dijkstra：

那次是很容易想到一个新的问题：最小生成树当中两个节点之间的距离是最短路径吗？

1 专门定义了一个类来比较小顶堆里面元素的大小，不知道如果单纯用一个bool类型的函数能不能行？

1. std::sort 与 priority_queue 的实现差异

2. 普通函数与函数对象的区别

3. std::sort 和 priority_queue 的设计目的不同

4. 函数指针和函数对象的不同

结论

1. 普通函数 vs 可调用对象

2. 为什么 Compare 是可调用对象，而普通函数不是？

2 定义了一个edge类型，还有构造函数，构造函数是为了后写 vector[left].push_back(Edge(right, val));的时候往里面直接插入edge类型的元素，但是为什么后面在定义有限对了的时候写的是priority_queue<pair<int, int> 而不是 priority_queue<Edge呢？

4 卡哥代码里面有这样一段：

94. 城市间货物运输 I

相关文章：

47. 参加科学大会（dijkstra（堆优化版）精讲）

1. `std::sort` 与 `priority_queue` 的实现差异

3. `std::sort` 和 `priority_queue` 的设计目的不同

2. 为什么 `Compare` 是可调用对象，而普通函数不是？