算法整理（更新中...）
算法整理
基础数据结构
数组
链表、双向链表
队列、单调队列、优先队列、双端队列
栈、单调栈
中级数据结构
堆
并查集、带权并查集
Hash表
自然溢出
双Hash
高级数据结构
树状数组
i + (i&-1)非常有意思，构造分形图案。i & (~i + 1)
线段树、线段树合并
平衡树
Treap
splay
替罪羊树
块状数组、块状链表
嵌套数据结构
树套树
DP套DP
可并堆
左偏树
配对堆
K-D Tree、四分树
可持久化数据结构
可持久化线段树
主席树
可持久化平衡树
可持久化并查集
可持久化块状数组
字符串算法
KMP
Manacher
Trie
AC自动机
后缀数组
后缀树
后缀自动机
图论算法
图的搜索
BFS DFS
基本思想：BFS使用队列，宽度优先；DFS使用递归写法or非递归(堆栈)实现，深度优先。
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> using namespace std; const int INF = 0x3f3f3f3f; const int MAX_V = 10; int V, E; int G[MAX_V][MAX_V];//邻接矩阵 struct Edge { int to, cost; Edge(int to, int cost): to(to), cost(cost) {}; }; vector<Edge> M[MAX_V];//邻接表 typedef pair<int, int> P;//first-to ,second-cost(unused) int visited[MAX_V]; void add_edge(int u, int v) { G[u][v] = 1; G[v][u] = 1; M[u].push_back(Edge(v, 0)); M[v].push_back(Edge(u, 0)); } void DFS1(int s) { //递归 邻接矩阵 cout << s << " "; visited[s] = 1; for (int i = 1; i <= V; i++) { if ( visited[i] == 0 && G[s][i] != INF) { DFS1(i); } } } void BFS1(int s) { //邻接矩阵 queue<int> q; q.push(s); while (!q.empty()) { int p = q.front(); q.pop(); if (visited[p] == 0) { cout << p << " "; } visited[p] = 1; for (int i = 1; i <= V; i++) { if (visited[i] == 0 && G[p][i] < INF) { q.push(i); } } } } void DFS2(int s) { //递归 邻接表 cout << s << " "; visited[s] = 1; for (int i = 0; i < M[s].size(); i++) { Edge e = M[s][i]; if ( visited[e.to] == 0) { DFS1(e.to); } } } void BFS2(int s) { //邻接表 queue<int> q; q.push(s); while (!q.empty()) { int p = q.front(); q.pop(); if (!visited[p]) { cout << p << " "; } visited[p] = 1; for (int i = 0; i < M[p].size(); i++) { Edge t = M[p][i]; if (!visited[t.to]) { q.push(t.to); } } } } void DFS3(int s) { //非递归 邻接矩阵 stack<int> _s; _s.push(s); while (!_s.empty()) { int p = _s.top(); if (!visited[p]) { cout << p << " "; visited[p] = 1; } int flag = 0; for (int i = 1; i <= V; i++) { if (!visited[i] && G[p][i] == 1) { // visited[i] = 1; // cout << i << " "; _s.push(i); flag = 1; break; } } if (flag == 0) { _s.pop(); } } } void DFS4(int s) { //非递归 邻接表 stack<int> _s; _s.push(s); while (!_s.empty()) { int p = _s.top(); if (!visited[p]) { cout << p << " "; visited[p] = 1; } int flag = 0; for (int i = 0; i < M[p].size(); i++) { Edge e = M[p][i]; if (!visited[e.to]) { // visited[i] = 1; // cout << i << " "; _s.push(e.to); flag = 1; break; } } if (flag == 0) { _s.pop(); } } } int main() { fill(G[0], G[0] + MAX_V * MAX_V, INF); cin >> V >> E; for (int i = 0; i < E; i++) { int u, v, w; cin >> u >> v; add_edge(u, v); } int st = 1; fill(visited, visited + MAX_V, 0); DFS1(st);//邻接矩阵 cout << endl; fill(visited, visited + MAX_V, 0); BFS1(st); cout << endl; fill(visited, visited + MAX_V, 0); DFS2(st);//邻接表 cout << endl; fill(visited, visited + MAX_V, 0); BFS2(st); cout << endl; fill(visited, visited + MAX_V, 0); DFS3(st); cout << endl; fill(visited, visited + MAX_V, 0); DFS4(st); cout << endl; return 0; } /* 8 9 1 2 1 3 2 4 2 5 4 8 5 8 3 6 3 7 6 7 */最短路径、次短路
连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。 强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
Dijkstra
基本思想（邻接矩阵表述）
设定两个集合\(A\)和\(B\)，\(A\)中存放我们已经处理过的顶点，\(B\)中存放图中剩余顶点。刚开始的时候，\(A\)中只有一个我们选定的起点\(v_0\)，每一次从集合\(B\)中取到\(v_0\)的代价最小的点并入，每一次并入时都需要修改\(v_0\)到\(B\)中顶点的代价，直到所有的顶点都并入为止。
算法准备
数组\(dist\)，用于存放\(v_0\)到图中个顶点的代价，数组下标表示顶点编号
数组\(path\)，用于存放路径，数组下标表示顶点编号，下标所对应的数组值表示能够到达当前这个顶点的前一个顶点编号，最后连起来就是\(v_0\)到图中各顶点的最短路径了。如果没有前前驱顶点，则内容值为-1。
数组\(set\)，用于标识图中顶点是否被处理过，数组下标表示顶点编号。处理过为1，没处理过为0。
使用图的邻接矩阵来存储有向带权图，\(graph[i][j]\)。
算法过程（我们选择编号为0的顶点作为起点）
- 首先进行3个数组的初始化，把set数组全部初始化为0；\(dist\)数组全部初始化为无穷大，\(path\)数组全部初始化为-1。
- 将\(set[0]\)的值设置为1，然后遍历邻接矩阵的第0行，依次更新\(dist\)数组的每一项。
- 将\(dist\)数组中值不为无穷大的在\(path\)中的对应下标，把它们的值改为0。因为编号为0的点是它们的前驱嘛。
- 选择\(dist\)数组中值最小的点的下标，这里为1。
- 将\(set[1]\)的值设置为1
- 遍历邻接矩阵的第1行(因为1是最小权值的下标)，将dist[1]的值与邻接矩阵\(graph[1][i]\)的值相加（此时是以编号为1的点作为中间点，看看由\(v_0\)->\(v_1\)再到其余点的路径长度会不会比\(v_0\)直接到它们的路径长度短），如果这个值比dist[i]的值小，就更新\(dist[i]\)，同时将\(path[i]\)的值设置为1，执行这个操作的前提是，\(set[i]==0\)。
- 重复（4）~（6）步，如果已经处理过的点就不用再判断了。直到\(set\)数组全变为1。
function Dijkstra(G, w, s) for each vertex v in V[G] // 初始化 d[v] := infinity // 将各点的已知最短距离先设成无穷大 previous[v] := undefined // 各点的已知最短路径上的前趋都未知 d[s] := 0 // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0 S := empty set Q := set of all vertices while Q is not an empty set // Dijkstra算法主体 u := Extract_Min(Q)//从Q中找一个距离远点s距离最小的点，加入S S.append(u) for each edge outgoing from u as (u,v) if d[v] > d[u] + w(u,v) // 拓展边（u,v）。w(u,v)为从u到v的路径长度。 d[v] := d[u] + w(u,v) // 更新路径长度到更小的那个和值。 previous[v] := u // 纪录前趋顶点//采用邻接矩阵存储 #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int INF = 0x3f3f3f3f; const int MAX_V = 10; int V, E; int G[MAX_V][MAX_V]; int dist[MAX_V]; int path[MAX_V]; int visited[MAX_V]; /* 采用邻接矩阵存储,需要设置visited数组判断是否已经访问过, 保证已计算出最短路的结点访问次数唯一, 作为对比可参考邻接表存储时的相应操作. */ void dijkstra(int s) { fill(path, path + MAX_V, -1); fill(visited, visited + MAX_V, 0); for (int j = 1; j <= V; j++) { dist[j] = G[s][j]; if (G[s][j] < INF) { path[j] = s; } } dist[s] = 0; visited[s] = 1; path[s] = 0; for (int i = 1; i <= V - 1; i++) { int minp = s, minw = INF; for (int j = 1; j <= V; j++) { if (visited[j] == 0 && dist[j] < minw) { minw = dist[j]; minp = j; } } visited[minp] = 1; for (int j = 1; j <= V; j++) { if (visited[j] == 0 && minw < INF && dist[j] > G[minp][j] + minw) { dist[j] = G[minp][j] + minw; path[j] = minp; } } } } void get_path(int ed) { if (path[ed] != -1) get_path(path[ed]); else return; cout << ed << "->"; } int main() { cin >> V >> E; fill(G[0], G[0] + MAX_V * MAX_V, INF); for (int i = 0; i < E; i++) { int u, v, w; cin >> u >> v >> w; G[u][v] = w; } int st = 2, ed = 1; dijkstra(st); get_path(ed); cout << "end" << endl; cout << dist[ed] << endl; return 0; }//采用邻接表存储 #include <iostream> #include <vector> #include <queue> using namespace std; const int INF = 0x3f3f3f3f; const int MAX_V = 10; struct Edge { int to, cost; Edge(int to, int cost): to(to), cost(cost) {};//C++初始化列表-构造函数内容：（参数列表，函数体，初始化列表） }; typedef pair<int, int> P;//first-to ,second-cost int V, E; vector<Edge> G[MAX_V]; int dist[MAX_V]; int path[MAX_V]; //bool visited[MAX_V]; /* 采用邻接表存储,不需要设置visited数组判断是否已经访问过, 因为采用优先队列维护已经保证访问次数唯一, 作为对比可参考邻接矩阵存储时的相应操作. */ void dijkstra(int s) { priority_queue<P, vector<P>, greater<P> > que; fill(dist, dist + V + 1, INF); fill(path, path + V + 1, -1); dist[s] = 0; path[s] = 0; que.push(P(s, 0)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.first; if (dist[v] < p.second) { continue; } /*细节问题！这里是剪枝操作，因为之前加入的点更新的距离可能已经不是最短， 此时找到了另外一条最短路，节点也更新，即在优先队列中存在多个相同顶点序号， 不同距离的pair<>，例如<2,3>,<2,2>（下面样例）会同时存在，显然，<2,3>这对数据没必要在运行*/ for (int i = 0; i < G[v].size(); i++) { Edge e = G[v][i]; if (dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; que.push(P(e.to, dist[e.to])); path[e.to] = v; } } } } void get_path(int ed) { if (path[ed]!=-1) get_path(path[ed]); else return; cout << ed << "->"; } int main() { cin >> V >> E; for (int i = 0; i < E; i++) { int u, v, w; cin >> u >> v >> w; G[u].push_back(Edge(v, w)); } int st = 1, ed = 4; dijkstra(st); get_path(ed); cout << "end" << endl; cout << dist[ed] << endl; return 0; } /* 5 7 1 2 1 1 3 4 1 5 1 2 4 5 5 2 1 5 3 2 3 4 2 */在最短路径问题中，对于带权有向图G = (V, E)，Dijkstra 算法的初始实现版本未使用最小优先队列实现，其时间复杂度为O(V2)，基于Fibonacci heap 的最小优先队列实现版本，其时间复杂度为O(E + VlogV)。
Bell-man Ford
算法思路
核心思想是：首先对距离进行松弛，然后随着迭代次数的增加，距离越来越接近最短路径，直到最后得出最短路径。更具体一点说就是每一次检查每一条边 \(<u,v>\) ,看是否有 \(d[v] > d[u] + L_{uv}\) 情况，如果有就更新 \(d[v]\) 的值，这样一来每一遍大的循环就把源点的情况全局推进一步，然后最多推进n-1步也就把原点的情况推到了每一个节点。
松弛：每次松弛操作实际上是对相邻节点的访问，第 \(k\) 次松弛操作保证了所有深度为 \(k\) 的路径最短。由于图的最短路径最长不会经过超过 \(|V|-1\) 条边，所以可知贝尔曼-福特算法所得为最短路径。
负边权操作：与迪科斯彻算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路；而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。
负权环判定：因为负权环可以无限制的降低总花费，所以如果发现第 \(n\) 次操作仍可降低花销，就一定存在负权环。
procedure BellmanFord(list vertices, list edges, vertex source) //读入边和顶点的列表并对distance和predecessor写入最短路径 // 初始化图 for each vertex v in vertices: if v is source then distance[v] := 0 else distance[v] := infinity predecessor[v] := null // 对每一条边重复进行“松弛”操作 for i from 1 to size(vertices)-1: // V - 1 次松弛 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // 检查图中包含有负权重的环 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "图中包含有负权重的环"#include <bits/stdc++.h> using namespace std; const int maxnum = 100; const int maxint = 0x3f3f3f3f; // 边， typedef struct Edge{ int u, v; // 起点，重点 int weight; // 边的权值 }Edge; Edge edge[maxnum]; // 保存边的值 int dist[maxnum]; // 结点到源点最小距离 int nodenum, edgenum, source; // 结点数，边数，源点 // 初始化图 void init(){ // 输入结点数，边数，源点 cin >> nodenum >> edgenum >> source; for(int i=1; i<=nodenum; ++i) dist[i] = maxint; dist[source] = 0; for(int i=1; i<=edgenum; ++i){ cin >> edge[i].u >> edge[i].v >> edge[i].weight; if(edge[i].u == source) //注意这里设置初始情况 dist[edge[i].v] = edge[i].weight; } } // 松弛计算 void relax(int u, int v, int weight){ if(dist[v] > dist[u] + weight) dist[v] = dist[u] + weight; } bool Bellman_Ford(){ for(int i=1; i<=nodenum-1; ++i) for(int j=1; j<=edgenum; ++j) relax(edge[j].u, edge[j].v, edge[j].weight); bool flag = 1; // 判断是否有负环路 for(int i=1; i<=edgenum; ++i) if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight){ flag = 0; break; } return flag; } int main(){ //freopen("input3.txt", "r", stdin); init(); if(Bellman_Ford()){ for(int i = 1 ;i <= nodenum; i++) cout << dist[i] << endl; } return 0; }复杂度O(VE)
SPFA
算法思路
算法思想：
我们用数组记录每个结点的最短路径估计值，用邻接表来存储图G。
我们采取的方法是动态逼近法：1.设立一个先进先出的队列用来保存待优化的结点。 2.优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。 3.这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。（?）
procedure Shortest-Path-Faster-Algorithm(G, s) for each vertex v ≠ s in V(G) d(v) := ∞ d(s) := 0 offer s into PQ //PQ是优先队列 while PQ is not empty u := poll PQ for each edge (u, v) in E(G) if d(u) + w(u, v) < d(v) then d(v) := d(u) + w(u, v) if v is not in PQ then offer v into PQ//bfs 万能啊 int spfa_bfs(int s){ queue <int> q; memset(d,0x3f,sizeof(d)); d[s]=0; memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; c[s]=1; //顶点入队vis要做标记，另外要统计顶点的入队次数 int OK=1; while(!q.empty()) { int x; x=q.front(); q.pop(); vis[x]=0; //队头元素出队，并且消除标记 for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表 { int y=v[k]; if( d[x]+w[k] < d[y]) { d[y]=d[x]+w[k]; //松弛 if(!vis[y]) //顶点y不在队内 { vis[y]=1; //标记 c[y]++; //统计次数 q.push(y); //入队 if(c[y]>NN) //超过入队次数上限，说明有负环 return OK=0; } } } } return OK; } //dfs处理负环更快，但是仅限于有限深度 int spfa_dfs(int u) { vis[u]=1; for(int k=f[u]; k!=0; k=e[k].next) { int v=e[k].v,w=e[k].w; if( d[u]+w < d[v] ) { d[v]=d[u]+w; if(!vis[v]) { if(spfa_dfs(v)) return 1; } else return 1; } } vis[u]=0; return 0; }时间复杂度是O(α(n)n)，n为边数，α(n)为n的反阿克曼函数，一般小于等于4
Floyd
算法思路
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为 \(O(N^3)\) ，空间复杂度为 \(O(N^2)\) 。Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点 u 到点 v 的最短路径，有两种情况：（1）直接从点 u 到 v 点（2）从点 u 经过若干个中间点 w 到点 v 。
算法描述：a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each vertex v dist[v][v] ← 0 for each edge (u,v) dist[u][v] ← w(u,v) // the weight of the edge (u,v) for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end ifvoid floyed(){//顶点的编号1~n for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dist[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]); } } } } } /* 4 8 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12 */ //传递闭包问题的修改版 void floyd(){ for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dp[i][j]=dp[i][j]||(dp[i][k]&&dp[k][j]); } } } }时间复杂度：\(O(n^3)\)
图的连通
强连通分量
tarjan，
双连通分量
割点、桥
网络流
用于解决流量问题。
网络流：所有弧上流量的集合\(f=\{f(u,v)\}\)，称为该容量网络的一个网络流(flow)。
定义：带权的有向图\(G=(V,E)\)，满足以下条件，则称为流网络(flow network)：
- 仅有一个入度为0的顶点，源点\(s\) (source)
- 仅有一个出度为0的顶点，汇点\(t\) (sink)
- 每条边\((u,v) \in E\)，都有一个非负权重 \(c(u,v)\)，表示边的容量(capacity)
性质：
对于任意一个时刻，设\(f(u,v)\)为实际流量，则整个图G的流网络满足3个性质：
- 容量限制：对任意\(u,v∈V\)，\(f(u,v)≤c(u,v)\)。
- 反对称性：对任意\(u,v∈V\)，\(f(u,v) = -f(v,u)\)。 每条边的流量与其相反边的流量之和为 0 。
- 流守恒性：\(\forall x \in V-\{s,t\}, \sum_{(u,x)\in E} f(u,x) = \sum_{(x,v)\in E} f(x,v)\) ，即，源点流出的流量等于汇点流入的流量。
剩余容量：\(c(u,v) - f(u,v)\)
整个网络的流量： 从源点发出的所有流量之和 \(\sum_{(s,v)\in E} f(s,v)\) 。
可行流：在\(G\)中，满足下列条件的网络流称为可行流：
- \(0 \leq f(u,v) \leq c(u,v)\)
- \(\sum_{e\in E^-(u)} f(e) = \sum_{e \in E^+(u)f(e)}\)， 即流入一个点的流量要等于流出这个点的流量
零流：若网络流上每条弧上的流量都为0，则该网络流称为零流。 伪流：如果一个网络流只满足弧流量限制条件，不满足平衡条件，则这种网络流为伪流，或称为容量可行流。
最大流：最大可行流。
割(cut)：割其实就是把节点分成两部分\((S,T)\) ，而且\(s\)位于\(S\)中，\(t\)位于\(T\)中。
最大流最小割(Max-flow min-cut)定理：网络流的最大流量等于最小割的容量。（最大流小于任意最小割的容量）
链：在容量网络中，称顶点序列\((u1,u2,u3,u4,..,un,v)\)为一条链，要求相邻的两个顶点之间有一条弧。 设\(P\)是\(G\)中一条从\(s\)到\(t\)的链,约定从s指向t的方向为正方向。在链中并不要求所有的弧的方向都与链的方向相同。
增广路径：
设\(f\)是一个容量网络\(G\)中的一个可行流，\(P\)是从\(s\)到\(t\) 的一条链，若\(P\)满足以下条件:
\(P\)中所有前向弧都是非饱和弧（流大小严格\(<\)容量）
\(P\)中所有后向弧都是非零弧
则称\(P\)为关于可行流\(f\)的一条增广路。
残留网络： 给定容量网络\(G(V,E)\)，及可行流\(f\)，弧\((u,v)\)上的剩余容量记为\(cl(u,v)=c(u,v)-f(u,v)\)。每条弧上的残留容量表示这条弧上可以增加的流量。因为从顶点\(u\)到顶点\(v\)的流量减少，等效与从顶点\(v\)到顶点\(u\)的流量增加，所以每条弧\((u,v)\)上还有一个反方向的残留容量\(cl(v,u)=-f(u,v)\)。
算法： EK（Edmond—Karp）算法，Ford-Fulkerson算（方）法，Dinic算法
最大流
我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。
最小割
割其实就是删边的意思，当然最小割就是割掉\(X\)条边来让\(s\)跟\(t\)不互通。我们要求\(X\)条边加起来的流量综合最小。这就是最小割问题，一般转化到最大流上。
网络流的割：是网络中顶点的一个划分，把所有顶点划分成两个顶点集合S和T，其中源点\(s\)属于\(S\)，汇点\(t\)属于\(T\)，记作\(CUT(S,T)\)。(包括正向边与反向边)
割的割边：如果一条弧的两个顶点一个属于顶点集\(S\)一个属于顶点集\(T\)，该弧为割\(CUT(S,T)\)的一条割边。
从\(S\)指向\(T\)的割边是正向割边；从\(T\)指向\(S\)的割边是逆向割边。
割的容量：所有正向割边的容量和，不同割的容量不同。
但注意，割的容量只记从\(S\)点集到\(T\)点集的而\(T\)点集到\(S\)点集的不算，所以割的容量等于这从\(S\)点集到\(T\)点集所有边的容量之和。
参考资料 [1]
费用流
最小费用最大流问题是这样的：每条边都有一个费用，代表单位流量流过这条边的开销。我们要在求出最大流的同时，要求花费的费用最小。
分数规划
无汇无源可行流
二分图
- KM算法
- Hungary算法、HK算法
最小生成树
1.Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。
2.Prim+Heap在任何时候都有令人满意的的时间复杂度，但是代价是空间消耗极大。【以及代码很复杂>_<】
3.时间复杂度并不能反映出一个算法的实际优劣。
Prim
算法思路
定义：一个连通图的生成树是一个极小的连通子图，它包含图中全部的顶点（n个顶点），但只有n-1条边。最小生成树是构造连通网的最小代价（最小权值）生成树。
最小生成树MST性质：假设N=（V,{E}）是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一颗包含边（u,v）的最小生成树。
Prim算法过程为：
书上是这么说的：假设N=（V,{E}）是连通图，TE是N上最小生成树中边的集合。算法从U={u_0}（u_0∈V），TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边（u，v）∈E中找一条代价最小的边（u0，v0）并入集合TE，同时v0 并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生成树。
此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。
图的所有顶点集合为V；初始令集合u={s}, v=V−u; 在两个集合u,v能够组成的边中，选择一条代价最小的边(u0,v0)，加入到最小生成树中，并把v0并入到集合u中。 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。 由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组mincost[MAX_V]，用来维护集合v中每个顶点与集合u中最小代价边信息。
/* wiki伪代码 从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。 输入：一个加权连通图，其中顶点集合为V，边集合为E； 初始化：Vnew={x}，其中x为集合V中的任一节点（起始点），Enew={}； 重复下列操作，直到Vnew = V： 在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； 将v加入集合Vnew中，将（u, v）加入集合Enew中； 输出：使用集合Vnew和Enew来描述所得到的最小生成树。 */主要过程是以“点”集合为中心算的，此外还可以使用Heap + Prim优化。
int cost[MAX _V][MAX _V]; //cost[u][v]表 示边e=(u,v)的权值(不存在的情况下设为INF ) int mincost[MAX_ V] ; //从集合X出发的边到每个顶点的最小权值 bool used[MAX_ _V]; // 顶点i是否包含在集合X中 int V; //顶点数 int prim() { for (int i = 0; i < V; i++) { mincost[i] = INF; used[i] = false; } mincost[0] = 0; int res = 0; while (true) { int v = -1; //从不属于X的顶点中选取从X到其权值最小的顶点 for (int u = 0; u < V; u++) { if (!used[u] && (v == -1 || mincost[u] < mincost[v])) { v = u; } } if (v == -1) break; used[v] = true; //把顶点v加入X res += mincost[v]; //把边的长度加到结果里 for (int u = 0; u < V; u++) { mincost[u] = min(mincost[u], cost[v][u]); } } return res;//返回MST权值 }复杂度：临接矩阵\(O(|V|^2)\) 邻接表 \(O(|E| log |V|)\)
Krusual
算法思路
克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用的最小边权的边（可以sort）。每次选择边权最小的边链接两个端点是kruskal的规则，并实时判断两个点之间有没有间接联通。
Kruskal算法原理如下。首先，将每个顶点放入其自身的数据集合中。然后，按照权值的升序来选择边。当选择每条边时，判断定义边的顶点是否在不同的数据集中。如果是，将此边插入最小生成树的集合中，同时，将集合中包含每个顶点的联合体取出，如果不是，就移动到下一条边。重复这个过程直到所有的边都探查过。
算法简单，需要使用到并查集。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m,tot=0,k=0;//n端点总数，m边数，tot记录最终答案，k已经连接了多少边 int fat[200010];//记录集体老大 struct node { int from,to,dis;//结构体储存边 }edge[200010]; bool cmp(const node &a,const node &b)//sort排序（当然你也可以快排） { return a.dis<b.dis; } int father(int x)//找集体老大，并查集的一部分 { if(fat[x]!=x) return father(fat[x]); else return x; } void unionn(int x, int y)//加入团体，并查集的一部分 { fat[father(y)]=father(x); } int main() { scanf("%d%d",&n,&m);//输入点数，边数 for(int i=1;i<=m;i++) { scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息 } for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大 （初始化） sort(edge+1,edge+1+m,cmp);//按权值排序（kruskal的体现） for(int i=1;i<=m;i++)//从小到大遍历 { if(k==n-1) break;//n个点需要n-1条边连接 if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体 { unionn(edge[i].from,edge[i].to);//加入 tot+=edge[i].dis;//记录边权 k++;//已连接边数+1 } } printf("%d",tot); return 0; }时间复杂度：O(|Elog|E|)
最小树形图
- 朱刘算法
欧拉图
环套树
仙人掌
树相关
树上倍增
最近公共祖先 LCA
树链剖分
动态树
- Link-Cut Tree
- 树分块
树分治
- 点分治
- 边分治
虚树
Prufer编码
拓扑排序
基于DFS的拓扑排序
摘录一段维基百科上的伪码： L ← Empty list that will contain the sorted nodes S ← Set of all nodes with no outgoing edges for each node n in S do visit(n) function visit(node n) if n has not been visited yet then mark n as visited for each node m with an edgefrom m to ndo visit(m) add n to LDFS的实现更加简单直观，使用递归实现。利用DFS实现拓扑排序，实际上只需要添加一行代码，即上面伪码中的最后一行：add n to L .需要注意的是，将顶点添加到结果List中的时机是在visit方法即将退出之时。这种方法十分巧妙。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000 + 10; const int INF = 1e9 + 7; int T, n, m, cases; vector<int>Map[maxn]; int c[maxn];//标记数组c[i] = 0 表示还未访问过点i， c[i] = 1表示已经访问过点i，并且还递归访问过它的所有子孙，c[i] = -1表示正在访问中，尚未返回 int topo[maxn], t; bool dfs(int u)//从u出发 { c[u] = -1;//访问标志 for(int i = 0; i < Map[u].size(); i++) { int v = Map[u][i]; if(c[v] < 0)return false;//如果子孙比父亲先访问，说明存在有向环，失败退出 else if(!c[v] && !dfs(v))return false;//如果子孙未被访问，访问子孙返回假，说明也是失败 } c[u] = 1; topo[--t] = u;//在递归结束才加入topo排序中，这是由于在最深层次递归中，已经访问到了尽头，此时才是拓扑排序中的最后一个元素 return true; } bool toposort() { t = n; memset(c, 0, sizeof(c)); for(int u = 1; u <= n; u++)if(!c[u]) if(!dfs(u))return false; return true; } int main() { while(cin >> n >> m) { if(!n && !m)break; int u, v; for(int i = 0; i <= n; i++)Map[i].clear(); for(int i = 0; i < m; i++) { cin >> u >> v; Map[u].push_back(v); } if(toposort()) { cout<<"Great! There is not cycle."<<endl; for(int i = 0; i < n; i++)cout<<topo[i]<<" "; cout<<endl; } else cout<<"Network has a cycle!"<<endl; } return 0; }Kahn算法
Kahn算法：
摘一段维基百科上关于Kahn算法的伪码描述： L← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edges while S is non-empty do remove a node n from S insert n into L foreach node m with an edge e from nto m do remove edge e from thegraph ifm has no other incoming edges then insert m into S if graph has edges then return error (graph has at least onecycle) else return L (a topologically sortedorder)不难看出该算法的实现十分直观，关键在于需要维护一个入度为0的顶点的集合：每次从该集合中取出(没有特殊的取出规则，随机取出也行，使用队列/栈也行，下同)一个顶点，将该顶点放入保存结果的List中。紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为0，那么也将这个顶点放到入度为0的集合中。然后继续从集合中取出一个顶点......当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果List，此List中的顺序就是对图进行拓扑排序的结果。
实现算法：博客链接
数论
- 欧几里得算法
- 扩展欧几里得算法
- 筛法
- 杜教筛
- 快速幂
- 裴蜀定理
- 欧拉函数
- 欧拉定理
- 费马小定理
- 排列组合
- Lucas定理
- 乘法逆元
- 矩阵乘法
- 数学概率与期望
- 博弈论
- SG函数
- 树上删边游戏
- 拉格朗日乘子法
- 中国剩余定理
- 线性规划
- 单纯形
- 辛普森积分
- 模线性方程组
- 莫比乌斯反演
- 莫比乌斯函数
- 容次原理
- 置换群
- FFT、NTT
- BSGS
- 扩展BSGS
动态规划
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。
参考资料 [1]
- 背包问题
- 概率DP
- 状压DP
- 区间DP
- 树形DP
- 数位DP
- 插头DP
- 斯坦纳树
- DP优化
- 单调队列优化
- 矩阵乘法优化
- 斜率优化
- 四边形不等式优化
计算几何
- 计算几何基础
- 梯形剖分
- 三角形剖分
- 旋转卡壳
- 半平面交
- pick定理
- 扫描线
搜索
- DFS、BFS
- A、IDA
- 迭代加深搜索
- 双向BFS
随机化
- 模拟退火
- 爬山算法
- 随机增量法
排序算法
这里将展示十中排序算法，包括内部排序和外部排序，各类排序算法的复杂度总结如下表：
！！！待插入汇总表
插入排序
直接插入排序
算法思想： 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。此方法可用于链表。
要点： 设立哨兵，作为临时存储和判断数组边界之用。
//插入排序 void Insert_Sort(int list[],int count){ int temp; /*此处充当哨兵，不在list数组里面单独占一个单位*/ int i,j; for(i=1;i<count;i++){ if(list[i]<list[i-1]){ temp = list[i]; for(j=i-1;list[j]>temp&&j>=0;j--){ list[j+1] = list[j]; } list[j+1] = temp; } } } // void Sort(int a[], int len){ for(int i=1;i<len;i++){ if(a[i]<a[i-1]){ int tmp = a[i]; int j; for(j=i-1;j>=0;j--){ if(tmp<a[j]){ a[j+1] = a[j]; }else break;//上面那个拆开就是这样 } a[j+1] = tmp; } } }折半插入排序
基本概念： 折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
算法思想： 在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素大，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
void BinaryInsertSort(int a[], int n) { int i, j, k, low, high, m; for(i = 1; i < n; i++) { low = 0; high = i - 1; while(low <= high) { //主要优化就是用二分法寻找有序数组的目标值 m = (low + high) / 2; if(a[m] > a[i]) high = m - 1; else low = m + 1; } if(j != i - 1) { int temp = a[i]; for(k = i - 1; k >= high + 1; k--) a[k + 1] = a[k]; a[k + 1] = temp; } } }希尔排序
基本思想： 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
排序过程： 先取一个正整数\(d_1<n\) ，把所有序号相隔 \(d_1\) 的数组元素放一组，组内进行直接插入排序；然后取 \(d_2<d_1\) ，重复上述分组和排序操作；直至 \(d_i=1\) ，即所有记录放进一个组中排序为止。
//shell排序，序号是0~count-1，序号如果从1开始，写法上有一点区别 //待排序数组和数组长度count void Shell_Sort(int a[], int len) { for (int d = len / 2; d >= 1; d /= 2) { for (int i = d; i < len; i++) { if (a[i] < a[i - d]) { int tmp = a[i]; int j; for (j = i - d; j >= 0; j -= d) { if (tmp < a[j]) { a[j + d] = a[j]; } else break; } a[j + d] = tmp; } } } }
交换排序
冒泡排序
算法思想：冒泡排序比较简单，俩层循环，第一层循环决定终止位置，第二层循环从起点位置开始遍历，到终止位置，其间对比相邻俩个元素，根据升序或者降序需求比较值并进行兑换。假设有一个大小为 N 的无序序列，冒泡排序就是要每趟排序过程中通过两两比较，找到第 i 个小（大）的元素，将其往上排。
void BubbleSort(int arr[], int n){//数组序号从0开始 for (int i = 0; i < n - 1; i++){ for (int j = 0; j < n - i - 1; j++){ if (arr[j] > arr[j + 1]){//递增排序，把大的先放到数组后面 swap(arr[j], arr[j + 1]); } } } } //逆序的写法，有序后加入flag提前退出 void BubbleSort(int arr[], int n){ for (int i = 0; i < n - 1; i++){ bool flag = false;//判断本轮的冒泡是否更新 for (int j = n-1; j > i; j--){//把小的先放到数组前面,本轮选择第i小的数字 if (arr[j-1] > arr[j]){//递增排序 swap(arr[j-1], arr[j]); flag = true; } } if(!flag)return; } }快速排序
算法思想： 随机找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个称为基准，然后就是比基准小的在左边，比基准大的放到右边，如何放做，就是和基准进行交换，这样交换完左边都是比基准小的，右边都是比较基准大的，这样就将一个数组分成了两个子数组，然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解为止。
算法流程： （1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； （2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]； （3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换； （4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换； （5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
#include<iostream> using namespace std; int partition(int arr[],int left,int right){ int temp=arr[left]; while(left<right)//直达left和right重合的时候，才找到合适的位置 { //先从后往前找比基准小的 while(left<right && arr[right]>=temp) //当right的值大于temp的值的时候才执行 //等号一定得写，因为可能会出现，保存的temp元素和数据中的元素一样的，不写会出现死循环的现象 { right--; } arr[left]=arr[right]; //当right的值小于temp的值的时候执行 //从前往后找，找比基准大的 while(left<right && arr[left] <=temp)//当left的值小于temp的值的时候执行 { left++; } arr[right]=arr[left];//当left的值大于temp的时候执行 } arr[left]=temp;//此时的left和right在同一个位置，此时为合适的位置，把temp的值给left return left;//此时返回的值是temp合适的位置，即小于它的在它的左边，大于它的在它的右边 } void quick(int arr[], int left, int right){ if(left<right){ int pivot=partition(arr,left,right); quick(arr,left,pivot-1); quick(arr,pivot+1,right); } } void quick_sort(int arr[],int len){ quick(arr,0,len-1); } int main(){ int arr[]={9,5,7,10,45,12}; int len=sizeof(arr)/sizeof(arr[0]); quick_sort(arr,len); for(int k=0;k<len;++k){ cout<<arr[k]<<" "; } cout<<endl; }int partition(int a[],int low,int high){ int tmp = a[low]; while(low<high){ while(low<high && a[high]>=tmp) --high; a[low] = a[high]; while(low<high && a[low]<=tmp) ++low; a[high] = a[low]; } a[low] = tmp; return low; } void quickSort(int a[], int low,int high) { if(low < high){ int pos = partition(a,low,high); quickSort(a,low,pos-1); quickSort(a,pos+1,high); } }快速排序的优化方法： 参考资料
（1）三数取中法，解决数据基本有序的（就是找到数组中最小下标，最大下标，中间下标的数字，进行比较，把中间大的数组放在最左边）
（2）随机选取基准，引入的原因是因为在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴，方法就是取待排序列中任意一个元素作为基准
（3）优化小数组的交换，就是为了解决大才小用问题，对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排，快排截止范围：待排序序列长度N = 10，虽然在5~20之间任一截止范围都有可能产生类似的结果，这种做法也避免了一些有害的退化情形
（4）在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割，具体过程：在处理过程中，会有两个步骤第一步，在划分过程中，把与key相等元素放入数组的两端，第二步，划分结束后，把与key相等的元素移到枢轴周围
选择排序
简单选择排序
算法思想：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
//选择排序 void Select_Sort(int list[],int count){ int min,i,j; for(i=0;i<count;i++){ min = i; for(j=i+1;j<count;j++){ if(list[min]>list[j]){ min = j; } } if(min!=i){ swap(list[i],list[min]); } } }堆排序
堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆是一种特殊的树形数据结构，即完全二叉树。堆分为大根堆和小根堆，大根堆为根节点的值大于两个子节点的值；小根堆为根节点的值小于两个子节点的值，同时根节点的两个子树也分别是一个堆。
算法思想：
- 步骤一：建立大根堆--将n个元素组成的无序序列构建一个堆，从最后一个非叶子节点开始向下调整。
- 步骤二：交换堆元素--交换堆尾元素和堆首元素，使堆尾元素为最大元素；
- 步骤三：重建大根堆--将前n-1个元素组成的无序序列调整为大根堆；
重复执行步骤二和步骤三，直到整个序列有序。
需要注意的是数组的序号可以从0开始也可以从1开始，写法上稍有不同，若初始序号是0，则对于序号是i的结点，
//调整为一个堆 void Heap_AdjustDown(int *list,int s,int m)//数组的序号的从1开始 { list[0] = list[s]; for(int j=2*s;j<=m;j = 2*j) { if(list[j]<list[j+1]&&j<m) { j++; } if(list[0]>list[j]) break; list[s] = list[j]; s = j; } list[s] = list[0]; } /*这样写也可以 void adjustDown(int a[],int k, int len){ a[0] = a[k]; for(int i=2*k;i<=len;i*=2){ if(a[i]<a[i+1]&&i<len)i++; //if(a[0]>a[i])break; if(a[i]>a[k]){ swap(a[i],a[k]);k = i; } else break; //a[k] = a[i]; } //a[k] = a[0]; } */ //堆排序 void Heap_Sort(int *list,int len)//数组的序号的从1开始 { //创建一个大顶堆 for(int s = len/2;s>0;s--) { Heap_AdjustDown(list,s,len); } //排序 for(int i = len;i > 1;i--) { swap(list[1],list[i]); Heap_AdjustDown(list,1,i-1); } }补充，堆的插入和删除：删除堆顶元素操作需要将堆顶元素与堆尾交换，由于破坏了堆的性质，需要向下调整Heap_AdjustDown。而插入元素操作，需要在堆尾插入，然后从堆尾开始向上调整Heap_AdjustUp。
void Heap_AdjustUp(int *list,int k)//数组的序号的从1开始，参数k是向上调整的节点位置(list[k])，也是堆元素个数;list[0]用作临时变量存放结点数字 { list[0] = list[k]; int i = k/2; while(i>0&&list[i]<list[0]){ list[k] = list[i]; k = i; i = k/2; } list[k] = list[0]; }另外一种写法，差不多。
//调整为一个堆，这个写法是0序号开始 void Heap_AdjustDown(int *list,int s,int m)//list是待排序数组，s是开始调整的父亲结点，m是堆尾结点的序号 { int temp = list[s]; for(int j=2*s+1;j<=m;j = 2*j+1) { if(j<m && list[j]<list[j+1]) { j++; } if(temp>list[j]) break; list[s] = list[j]; s = j; } list[s] = temp; } //堆排序 void Heap_Sort(int *list,int len) { //创建一个大顶堆 for(int s = len/2-1;s>=0;s--) { Heap_AdjustDown(list,s,len-1); } //排序 for(int i = len-1;i >= 1;i--) { swap(list[0],list[i]); Heap_AdjustDown(list,0,i-1); } }void Heap_AdjustUp(int *list,int k)//数组的序号的从0开始，参数k是向上调整的节点位置，也是堆元素个数 { int tmp = list[k]; int i = (k-1)/2; while(i>=0&&list[i]<tmp){ list[k] = list[i]; k = i; i = (k-1)/2; if(k==0)break;//这里跳出，有空再改 } list[k] = tmp; }n个元素建立堆的时间复杂度是O(n)，调整堆的时间复杂度是O(h)
归并排序
算法思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
//非递归 int min(int x, int y) { return x < y ? x : y; } void merge_sort(int arr[], int len) { int *a = arr; int *b = (int *) malloc(len * sizeof(int)); int seg, start; for (seg = 1; seg < len; seg += seg) { for (start = 0; start < len; start += seg * 2) { int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high; while (start1 < end1 && start2 < end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) b[k++] = a[start1++]; while (start2 < end2) b[k++] = a[start2++]; } int *temp = a; a = b; b = temp; } if (a != arr) { int i; for (i = 0; i < len; i++) b[i] = a[i]; b = a; } free(b); }//递归 //merge_sort_recursive（待排序数组，辅助数组，起始位置，结束位置） void merge_sort_recursive(int arr[], int reg[], int start, int end) { if (start >= end) return; int len = end - start, mid = (len >> 1) + start;//mid = (len)/2 + st int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; merge_sort_recursive(arr, reg, start1, end1); merge_sort_recursive(arr, reg, start2, end2); int k = start; while (start1 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; while (start1 <= end1) reg[k++] = arr[start1++]; while (start2 <= end2) reg[k++] = arr[start2++]; for (k = start; k <= end; k++) arr[k] = reg[k]; } void merge_sort(int arr[], const int len) { int reg[len]; merge_sort_recursive(arr, reg, 0, len - 1); }基数排序
两种多关键码排序方法：最高位优先(Most Significant Digit first)法，简称MSD 法；最低位优先(Least Significant Digit first)法，简称LSD 法。实现方法是将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
int maxbit(int data[], int n) //辅助函数，求数据的最大位数 { int maxData = data[0]; ///< 最大数 /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。 for (int i = 1; i < n; ++i) { if (maxData < data[i]) maxData = data[i]; } int d = 1; int p = 10; while (maxData >= p) { //p *= 10; // Maybe overflow maxData /= 10; ++d; } return d; /* int d = 1; //保存最大的位数 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d;*/ } void radixsort(int data[], int n) //基数排序 { int d = maxbit(data, n); int *tmp = new int[n]; int *count = new int[10]; //计数器 int i, j, k; int radix = 1; for(i = 1; i <= d; i++) //进行d次排序 { for(j = 0; j < 10; j++) count[j] = 0; //每次分配前清空计数器 for(j = 0; j < n; j++) { k = (data[j] / radix) % 10; //统计每个桶中的记录数 count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶 for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; } delete []tmp; delete []count; }外部排序算法之多路归并排序
其他
分治
- CDQ分治
- 整体二分
莫队算法
- 树上莫队算法
- 待修改莫队算法
分块
高精度
离线
RMQ
- ST表
二分法
二分答案
二分查找
三种写法不一样 能够写对一种就好，注意溢出。
在这里再补充一下lowerbound和upperbound
//用这个!!!!!!!!!! int binarySearch(int a[],int l,int r,int tar){ while(l<r){//返回[l,r)中第一个不小于tar的值的下标 int mid = l + (r-l)/2; if(a[mid] >= tar) r = mid; else l=mid+1; } return l; }bool bSearch(int a[], int left, int right, int tag) { while(left <= right){ int mid = (left + right) >> 1; if (a[mid] == tag) return true; else a[mid] < tag ? left = mid + 1 : right = mid - 1; } return false; } //求解区间[l,r]**ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)**算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。
**ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)**算法返回一个非递减序列[first, last)中第一个大于val的位置。
int upperBound(int a[], int l, int r,int tag){//[l,r)区间求解UB while(l < r) {//在[l,r]求LB,等于[l,l+len) int mid = (l + r) / 2; if(a[mid] > tag) r = mid; else l = mid+1; } return l;//写return l不会错 }int lowerBound(int a[], int l, int r, int tag){ while(l<r){//在[l,r)求LB,等于[l,l+len) int mid = (l+r)/2; if(a[mid]>=tag)//求上下界的区别在于等号的处理 r = mid; else l = mid+1; } return l; } //求上下界的区别在于等号的处理,下界的等号与">"合并,因为要取得tag的值的索引必定比mid大,而有边界好取lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。
在从小到大的排序数组中：
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从大到小的排序数组中，重载lower_bound()和upper_bound()：
lower_bound( begin,end,num,greater
() ): 从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。upper_bound( begin,end,num,greater
() ): 从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。原文链接：https://blog.csdn.net/qq_40160605/article/details/80150252
应用一：upper_bound - lower_bound = target的数量
[0,1,1,2,2，2,3,4,5,6] lower_bound(2) --> 3(下标) upper_bound(2) --> 6(下标) 可以得到2的个数是3
三分法
贪心
模拟
P类问题：存在多项式时间算法的问题。(P：polynomial，多项式)
NP类问题：能在多项式时间内验证得出一个正确解的问题。(NP:Nondeterministic polynomial，非确定性多项式)P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证他。注意定义，这里是验证。NP类问题，我用个人的俗话理解就是，不知道这个问题是不是存在多项式时间内的算法，所以叫non-deterministic非确定性，但是我们可以在多项式时间内验证并得出这个问题的一个正确解。举个例子，
NPC问题：如果所有np问题都能在多项式时间内转化为他，则称该np问题为npc问题(NPC:NP complete又叫NP完全问题)NPC问题是NP问题的子集。
NPH问题：我们又叫NP难问题，他不是一个NP问题，然后所有的NPC问题都可以在多项式时间内转化为他的话，我们就叫他NPH（hard）问题。
牛顿迭代法
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！