题解 P1828 【香甜的黄油 Sweet Butter】- 优先队列

Meatherm · 2019-01-27 10:17:01 · 题解

我觉得这道题目里面的dijkstra堆优化不适合竞赛党，所以我就重新发了一篇语法比较标准的，希望对大家有帮助。但是，该题解因为从零开始介绍了多种STL/C++特殊语法，所以看下来还是需要勇气的。

=========↓忙人请跳过分割线内的内容↓=========

这道题是一个比较坑的题目。。。我交了5次才过。

瞎扯一下我的辛酸史：

1. floyd写错--10分
2. floyd写对了但是超时--80分
3. 迪杰斯特拉堆优化（优先队列优化）写错--10分
4. 迪杰斯特拉堆优化（优先队列优化）写对但是用的邻接矩阵TLE--70分
5. 取得真经（迪杰斯特拉堆优化+邻接表）--AC

=========↑忙人请跳过分割线内的内容↑=========

简述dijkstra堆（优先队列）优化

在裸的dijkstra中，我们发现，我们每次都要O(n)的复杂度来寻找和当前点距离最近的点。于是，我们很自然的想到可以用数据结构来优化复杂度。这次我们选到的是STL优先队列。（接下来会介绍在这道题里面优先队列会使用的基本操作）

STL的内部结构是二叉堆（不懂二叉堆的同学戳这里和这里）。它插入元素、取出元素的时间复杂度均为O(logN)。有同学要问了：取出元素不是O(1)吗？因为取出元素后还要维护最小（最大）堆的特性，所以其实是O(logN)。

优先队列我们要用到的操作：

1. 定义一个优先队列

   priority_queue <类型名> 队列名称;

   例：

   priority_queue <int> k;//k为自定义名称

2. 插入一个元素（2~5操作不会举例）

   队列名称.push(元素名称);

3. 删除队首元素

   队列名称.pop();

4. 返回队列的元素个数

   队列名称.size();//返回值为整数，返回队列的元素个数

5. 返回队列是否为空

   队列名称.empty();//返回值为布尔值，返回true表示队列为空，反之不为空

优先队列默认是把元素从大到小排序。

例如我一次性插入5个元素：

3 4 2 5 1

那么5次弹出时依次是：

5 4 3 2 1

而在图论题目中，我们常常要使用结构体，这时候系统会怎样排序呢？我们不清楚。这个时候，我们就需要重载运算符。

==========我是分割线============

不得不提的：重载运算符

重载运算符就是将一个运算符原来的运算方式改变。但是，重载运算符在一般使用中要注意三点：

第一、不改变返回值类型

拿C++的运算符%和&&来举例，%的返回值是一个整数，代表两个整数相除的余数。&&是逻辑与，返回的是bool值，代表表达式中两个条件是否同时成立。

假设%返回了一个字符串，&&返回了一个整数...

这时候，编译就会出错。因为C++的运算符重载是不能改变返回值类型的。

第二、不改变运算目数（不改变运算参数数量）

什么是运算目数？在进行+运算时，我们要写成元素1 + 元素2的这种形式，也就是说，+要有两个参数元素1和元素2才能进行运算，那么+的目数就是2。同样的，? :是三目运算符，!是单目运算符。在重载时，同样也不能改变运算目数（运算参数数量）。

第三、不能创造新的运算符

重载运算符过程中，只能从现有运算符选择一个进行重载，例如重载@就是错的，因为@不是一个运算符。