首页 > 笔记 > NOIP算法总结

NOIP算法总结

临时抱佛脚

1.图论

最短路

1.堆优化dij

用priority_queue做堆,对于每次弹出的点

标记访问

对于所有能访问到的点

松弛

若未访问,压到堆中

2.spfa

用queue做队列,对于每次弹出的点

消除标记

对于所有能访问的点

松弛

若未标记,则标记,进入队列

最小生成树

1.kruskal

并查集初始化

边权排序

假如边上两点不在同一集合内

合并两点

把边加入最小生成树

2.prim

不大常用。。。懒得写了

强连通分量Tarjan

对于dfs每次到的节点

初始化dfn[x]=low[x]=++dfs_clock

把节点压到栈中

对于所有能访问的节点

如果dfn为0(未dfs到)

dfs那个节点

更新low(low[x]=min(low[x],low[那个节点]);)

若不为0且在不在栈中

low[x]=min(low[x],dfn[那个节点]);

如果low[x]==dfn[x]

弹出栈中的元素,直到弹出的元素等于x,弹出的元素都属于一个强连通分量

没测试完。。。

2.排序

sort。。。【stl大法好

3.数论

直接上程序了【懒得讲

4.高精度

没啥好说的

直接重载

 

 


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×