Dijkstra 堆优化

发表于 2023-01-03 更新于 2025-07-20 分类于程序设计竞赛

Dijkstra 堆优化

回顾

迪杰斯特拉-算法回顾 1. 准备工作：设置辅助数组 Dist，其中每个分量 Dist[k] 表示：当前所求得的从源点到其余各顶点k的最短路径。 2. 在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。 3. 修改其它各顶点的 Dist[k] 值。 4. 选出下一条最短路，回到步骤 3，直到求出所有最短路。

堆优化

dist最小值使用priority_queue维护 邻接表：空间+时间优化 O(ElogE)E是边数原因在于堆不容易删去指定节点代码

阅读全文 »

拓补排序+邻接表

发表于 2023-01-03 更新于 2025-07-20 分类于程序设计竞赛

拓补排序+邻接表

拓补排序定义

需要在有向无环图中

所谓“拓扑排序”，是指将一个有向无环图G的所有顶点排成一个线性序列，使得有向无环图G的边集中的任意一条边<u, v>，始终满足u出现在v的前面。

通常，这样的序列称为是“拓扑序列”。

拓扑排序算法基本思想

阅读全文 »

离散化

发表于 2023-01-03 更新于 2025-07-20 分类于程序设计竞赛

离散化

例题

给定n (n<=100000)个正整数Ai组成的数列(Ai<=10^9, 1<=i<=n)，希望对该数列从小到大排序，如果采用冒泡排序算法，请计算需要进行的交换次数。

阅读全文 »

树状数组

发表于 2023-01-02 更新于 2025-07-20 分类于程序设计竞赛

树状数组

树状数组定义

奇数上总是本元素偶数会包含前面的元素

// 将C数组的下标i转化成二进制:
1=(001) C[1]=A[1];
2=(010) C[2]=A[1]+A[2];
3=(011) C[3]=A[3];
4=(100) C[4]=A[1]+A[2]+A[3]+A[4];
5=(101) C[5]=A[5];
6=(110) C[6]=A[5]+A[6];
7=(111) C[7]=A[7];
8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];