2022-2023算法总结
2022-2023算法总结
一、图论
1.图的基本概念
-
图：二元组
G(V,E) 称为图，其中，V 为结点或顶点集，E 为图中结点之间边的集合。 -
点：用数字
0\cdots n-1 表示。 -
边：点对
(u,v) 称为边或称弧。对于边(u,v)\in E ，u 和v 邻接，e 和u,v 关联。 -
子图：边的子集和相关联的点集。
-
有向边：表示以
u 为起点,v 为终点的边。 -
无向边：表示既能从
u 到v ，又能从v 到u 的边。 -
有向图：边都是有向边，是单向的。
-
无向图：边都是无向边，是双向的。
-
带权图：图的边带一个权值，表示具体的含义，例如距离，费用，拥堵程度等等。权值可以是正值，也可以是0或负值。
-
图的稠密性：
n 为顶点数，边数和n(n-1)/2 相比非常少的图称为稀疏图，反之为稠密图。 -
完全图：边数为
n(n-1)/2 的图称为完全图。 -
点的度：图中与某一个点相连的边数称为该点的度。
-
出度 / 入度：在有向图中，从
u 出发的边的数量称为u 的出度，到达u 的边的数量称为u 的入度。 -
连通图：如果图中任意两点都有路径相连，则称该图是连通图，否则称图为非联通的。
-
树：一种特殊的图，是
n 个点，n-1 条边的连通图（无环连通图）。 -
重边：端点和方向（有向图）完全相同的边称为重边。
-
自环：连接相同点的边称为自环。
2.图的存储
图的存储有两种常见方式，分为邻接矩阵和邻接表（ vector 和链式前向星）。
- 邻接矩阵
设图中有
5.拓扑排序
DAG：有向无环图
在一个DAG中，一条有向边的起点叫做其终点的前驱节点，同理，终点是起点的后继结点。
把 DAG 中所有活动排成一个序列，使得每个活动的所有前驱都在该活动的前面，这个过程叫拓扑排序。 （拓扑排序的结果可能并不唯一）
拓扑排序的过程？
-
选择一个入度为 0 的顶点并输出
-
然后从 DAG 中删除此顶点以及其关联边
-
重复上述两步，直到不存在入度为 0 的顶点为止
-
结论：若一个有向图在拓扑排序后输出的顶点数小于原图中的顶点数，则原图必定存在环，即原图不是一个 DAG。
如何实现？
首先统计每个点的入度，使入度为0的点入队，队首指针的点的关联边的 to 点入度减 1 ，继续第二步直到队列为空，也就是所有点的入度均为 0 。最后队列数组的内容就是拓扑排序的结果。
代码实现：
#include <bits/stdc++.h>
using namespace std;
void add_edge(int from, int to){
edge[++edgenum].next = head[from];
edge[edgenum].from = from;
edge[edgenum].to = to;
head[from] = edgenum;
++in[to];
}
void topo_sort(){
cin >> n >> m;
int h = 0, t = 0;
for(int i = 1; i <= n; i++)
if(in[i] == 0) q[t++] = i;
while(h <= t){
int x = q[h++];
for(int i = head[x]; i; i = edge[i].next){
--in[edge[i].to];
if(!in[edge[i].to])
q[t++] = edge[i].to;
}
}
}
6.最小生成树
相关概念：
-
生成树：在一个有
n 个顶点的无向连通图中，取其中n-1 条边，使得所有顶点都连通，所得到的子图为原图的一棵生成树. -
最小生成树：在一个带权的无向连通图中，各边权和最小的一棵生成树即为原图的最小生成树。
-
对于一个边权值都不相同的图来说，最小生成树是唯一的，反之不然。
主要介绍两种算法： Prim 算法和 Kruskal 算法
- Prim 算法
Prim 算法基于贪心思想，它将无向连通图
最开始
实现步骤：
-
用
d_i 表示集合Vb 中的点到Va 中的点的距离值。初始化d_{v0}=0 ，其余的点d_i=INF 。 -
经过
n 次如下步骤操作：
选择一个未标记的点
- 得到最小生成树。
代码实现：
邻接矩阵存图：
void prim(int v0){
int minn;
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[v0]=0;
for(int i=1;i<=n;i++){
minn=INF;
for(int j=1;j<=n;j++){
if(vis[j]==0 && minn>dis[j]){
minn=dis[j];
k=j;
}
}
vis[k]=1;
ans+=minn;
for(int j=1;j<=n;j++){
if(vis[j]==0 && dis[j]>g[k][j])
dis[j]=g[k][j];
}
}
}Vector 存图：
#include <bits/stdc++.h>
using namespace std;
void Prim(int v0){
int mark, minn, ans = 0;
for(int i = 1; i <= n; i++)
d[i] = INF;
d[v0] = 0;
for(int i = 1; i <= n; i++){
minn = INF;
for(int j = 1; j <= n; j++)
if(!vis[j] && minn > d[j]){
minn = d[j];
mark = j;
}
vis[mark] = 1;
for(int j = 0; j < E[mark].size(); j++){
int v = E[mark][j].first;
if(!vis[v] && d[v] > E[mark][j].second)
d[v] = E[mark][j].second;
}
}
}算法优化：
暴力 Prim 算法的时间复杂度：每一个点要扫一遍所有点求最小
堆优化 Prim 算法的时间复杂度：每条边的边权值会用来更新
- Kruskal 算法思想
也是基于贪心思想。首先将边按权值排序，每次从剩下的边集中选择权值最小的且与不前面所选边构成环的边加入生成树中，直到加入了
判断环用并查集：待加边的两个端点若已在生成树中，则必定构成环。
时间复杂度为：
代码实现：
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[5005],cnt,ans;
struct node{
int u,v,w;
}a[200005];
bool cmp(node p,node q){
return p.w<q.w;
}
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);//并查集的基础上
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
cin>>a[i].u>>a[i].v>>a[i].w;
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++){
int t1,t2;
t1=find(a[i].u);
t2=find(a[i].v);
if(t1!=t2){
fa[t1]=t2;
cnt++;
ans+=a[i].w;
}
if(cnt==n-1) break;
}
if(cnt==n-1) cout<<ans;
else cout<<"orz";//判负权环
return 0;
}7.最近公共祖先（LCA）
最近公共祖先简称 LCA ，所谓 LCA ，是当给定一个有根树
如上图，结点 3 和结点 4 的最近公共祖先是结点 2 ，即
LCA 的基础性质
-
\operatorname{LCA} (u) =u -
u$ 是 $v$ 的祖先，当且仅当$\operatorname{LCA} (u,v) =u -
如果
u 不为v 的祖先并且v 不为u 的祖先，那么u ，v 分别处于\operatorname{LCA} (u,v) 的两棵不同子树中 -
前序遍历中，
\operatorname{LCA} (S) 出现在所有S 中元素之前，后序遍历中\operatorname{LCA} (S) 则出现在所有S 中元素之后 -
两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即
\operatorname{LCA} (A \cup B)=\operatorname{LCA}(\operatorname{LCA}(A),\operatorname{LCA}(B)) -
两点的最近公共祖先必定处在树上两点间的最短路上
-
_**LCA 的朴素求法**_
可以每次找深度比较大的那个点，让它向上跳。显然在树上，这两个点最后一定会相遇，相遇的位置就是想要求的 LCA 。
或者先向上调整深度较大的点，令他们深度相同，然后再共同向上跳转，最后也一定会相遇。
朴素算法预处理时需要 dfs 整棵树，时间复杂度为
倍增算法求 LCA？
朴素算法的改进算法。
通过预处理
代码实现：
void dfs(int u, int fa){
dep[u] = dep[fa] + 1;
for(int i = 0; i <= 19; i++)
fa[u][i+1] = f[f[u][i]][i];
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if(v == fa) continue;
f[v][0] = u;
dfs(v, u);
}
}
//预处理出每个点的深度和f数组
int lca(int x, int y){
if(dep[x] < dep[y]) swap(x, y);
for(int i = 20; i >= 0; i--){
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
if(x == y) return x;
}
for(int i = 20; i >= 0; i--){
if(f[x][i] != f[y][i]){
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}upd：在写lca例题的一点感想。
lca算法所用到的倍增思想非常经典，st表也是运用了相似的倍增思想，所以可以积累一下（。
还有tarjan求lca的方法，有些神秘题里还是有必要的。（虽然我不会！）
8.强联通分量
相关基本概念
-
强联通：在一个有向图
G 中，如果两个顶点u 、v 间存在一条u 到v 的路径且也存在一条v 到u 的路径，则称这两个顶点u 、v 是强连通的。 -
强联通图：有向图
G 的任意两个顶点都强连通，则称G 是一个强连通图。 -
极大强连通子图：
G 是一个极大强连通子图，当且仅当G 是一个强连通子图且不存在另一个强连图子图G'\supset G 。 -
强联通分量：有向非强连通图的极大强连通子图，称为强连通分量。
图例：（先鸽着）
Tarjan 算法求强联通分量
图示：鸽着。懒得写了。
代码实现：
void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
vis[u]=1;
st.push(u);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u], low[v]);
}
else if(vis[v])
low[u]=min(low[u], dfn[v]);
}
if(dfn[u]==low[u])
{
tot++;
int v;
do
{
v=st.top();
st.pop();
col[v]=tot;
vis[v]=0;
}while(v!=u);
}
}很经典的一道题：采蘑菇（算是 SPFA 和缩点的有机合成物？）
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 8e4 + 10, M = 2e5 + 10;
int n, m, t, cnt, tot, T, s, ans;
int head[N], dfn[N], low[N], vis[N];
int col[N], H[N], sum[N], dis[N], V[N];
struct edge
{
int from, to, next, val, k;
} e[M], E[M];
stack<int> st;
queue<int> q;
void addedge(int u, int v, int w, int k)
{
e[++t] = (edge){u, v, head[u], w, k};
head[u] = t;
}
void add(int u, int v, int w)
{
E[++T].to = v;
E[T].next = H[u];
E[T].val = w;
H[u] = T;
}
void tarjan(int u)//tarjan缩点模板
{
dfn[u] = low[u] = ++cnt;
vis[u] = 1;
st.push(u);
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (vis[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
tot++;
int v;
do
{
v = st.top();
st.pop();
col[v] = tot;
vis[v] = 0;
} while (v != u);
}
}
void spfa(int s)//spfa跑最长路
{
memset(dis, -1, sizeof(dis));
memset(V, 0, sizeof(V));
dis[s] = sum[s];
V[s] = 1;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
V[u] = 0;
for (int i = H[u]; i; i = E[i].next)
{
int v = E[i].to, w = E[i].val;
if (dis[v] < dis[u] + w + sum[v])
{
dis[v] = dis[u] + w + sum[v];
if (!V[v])
{
V[v] = 1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int x, y, z;
double k;
scanf("%d%d%d%lf", &x, &y, &z, &k);
addedge(x, y, z, k * 10);//先让恢复系数乘10
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= m; i++)
{
int x = e[i].from, y = e[i].to, z = e[i].val, k = e[i].k;
if (col[x] == col[y])
while (z)//同一个强连通分量就统计蘑菇数
{
sum[col[x]] += z;
z = z * k / 10;//再整除10
}
else
add(col[x], col[y], z);//不是同一个强连通分量就建边
}
scanf("%d", &s);
s = col[s];
spfa(s);
for (int i = 1; i <= tot; i++)
ans = max(ans, dis[i]);//终点是未知的，所以通过比较dis找到最长路
printf("%d\n", ans);
return 0;
}9.双连通分量
相关概念：
-
割点：无向连通图中，某点和其邻接边去掉后，图不再连通。
-
桥：同理，无向连通图中，某边去掉后，图不再连通，又称割边。
（这里有两张图，先鸽了。我是鸽子。）
Tarjan 求割点
暴力求解割点的方法就是枚举每个点，然后再 dfs 整个图看是否连通，复杂度太高。
考虑使用 Tarjan 算法，设