发表更新学习总结 / 图论 / 最短路6 分钟读完 (大约891个字)

最短路技巧

前置知识：图论基础，最短路基础

Super Root 超级源点、加点、加边

特征

  • 需要添加边，但是暴力加边时间or空间复杂度不可取；
  • 加边是针对某一类点加边；
  • 答案最终会汇集到一个点上，一些网络流的题需要建立超级源点和超级汇点。

注意点

  • 加边时考虑边权设计；
  • 如果要对超级源点加双向边，要考虑周全一些不合法的情况，例如会不会无边权超级传送；
  • 加点要算好空间，算好下标。

例题

给定一棵树，$1$ 为根节点，对于树上每条边 $(u, v)$ 都具有一个权值 $w$ 。但是，如果两个节点的高度差为 $k$ ，则可以通过 $p$ 的权值直接到达，求在这棵树上从 $s$ 到 $t$ 的最短路径长度。
多组测试数据。
$1 \le T \le 5$
$2 \le n \le 10^6$
$1 \le u_i,v_i,s,t \le n, u_i \neq v_i, s \neq t$
$1 \le w_i,k \le 10^6$
$0 \le p \le 10^6$

我们发现这道题需要加边跑最短路，然而，$\text{Dijkstra}$ 带上加边会跑到 $O((n+m+n^3)\log (m+n^3)+n^3)$ ，这里极限数据的情况是整棵树有 $\sqrt n$ 层，每层有 $\sqrt n$ 个点，且 $k = 1$ 。即使我们不真正连边，仍然还有 $O((n+m+n^3)\log (m+n^3))$ 的时间复杂度。死得透透的。

因此我们考虑对每一层建立一个超级源点，边权为 $0$ ，再对上下 $k$ 层的超级源点连边，因为这个点既可以上又可以下，所以要连双向边。然鹅，这个方案有一个巨大的问题。

如果我们连双向边，那么最短路会借助超级源点在同一层实现 $0$ 权值跳转，很明显，这是不合法的。于是我们考虑每层加两个超级源点，一个用于向外走，一个向内走，问题就解决了，时间复杂度 $O((5n+m)\log (2n+m))$ 。

给出一个图，每次只能连续走两条边，其权值为两条边权值的和的平方，求以 $1$ 为源点时分别到 $1\sim n$ 的最短路。
$2 \leqslant n \leqslant 10^5,1 \leqslant m\leqslant min(\frac{n(n-1)}{2},2*10^5)$
$1\leqslant v_i,u_i \leqslant n,1 \leqslant w_i \leqslant50,u_i\neq v_i$

同时处理两条边是有些困难的。考虑往图里增加信息。我们发现边权十分小，只有 $50$ 。于是我们想到建分层图，入边 $(u,v,w)$ 即建一条边从第 $w$ 层图 $v$ 点到原图 $v$ 点，出边 $(u,v,w)$ 就是建一条边从原图 $v$ 点到第 $w$ 层图 $v$ 点。这样做正确性显然。

2. 最短路计数

这里要提两个概念

附录

SPFA玄学优化

据某位不知名人士所言，SPFA的时间复杂度可以用 $O(m+n\log n)$ 来拟合，而Dijkstra的时间复杂度为 $O(m\log n)$ 。这意味着如果题目不卡SPFA，则SPFA跑得比Dijkstra还要快。如果卡SPFA，还可以通过SLF、mcfx等优化方法来使SPFA更快。甚至专门卡SPFA的标准版单源最短路径的次优解（$\text{80ms}$）就是使用了SLF-swap优化过的。

发表更新学习总结 / 图论2 分钟读完 (大约337个字)

图论基础

存图

邻接矩阵

实现：

1
2
3
4
5
6
7
8
int g[N][N];

g[u][v] = w;

for (int v = 1; v <= N; v++) {
    if (!g[u][v]) continue;
    // ...
}

空间复杂度：$O(n^2)$

优点

  • 配合Floyd算法，效果嘎嘎好
  • 支持随机访问，即直接查询某条边是否存在
  • 代码好写

缺点

  • 空间复杂度太高，是个硬伤

邻接表

实现：

1
2
3
4
5
6
7
8
vector<pair<int, int>> g[N];

g[u].push_back({v, w});

for (pair<int,int> i : g[u]) {
    int v = i.first, w = i.second;
    // ...
}

空间复杂度：$O(m)$

优点

  • 空间复杂度小
  • 同一个点空间连续，有效降低Memory Cache带来的时间花销
  • 写循环遍历 $u$ 边时可以少写点代码：for (pair<int,int> i : g[u])

缺点

  • 由于 vector ，空间复杂度要翻个倍，在卡空间的题目中它不是好选择
  • 莫名其妙TLE（STL造成的）

链式前向星

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct node{
    int to, nxt, w;
}g[M];
int head[N], cnt;

void add(int u, int v, int w) {
    g[++cnt] = {v, head[u], w};
    head[u] = cnt;
}

for (int i = head[u]; i; i = g[i].nxt) {
    int v = g[i].to, w = g[i].w;
    // ...
}

空间复杂度：$O(m)$

优点

  • 空间复杂度真的小，没有 vector 的两倍空间限制

缺点

发表更新学习总结 / 图论24 分钟读完 (大约3568个字)

二分图与图的连通

update: 2023/12/12 fixed pictures

学习内容

本周学习内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Week 1
|- 二分图
|  |- 二分图的判定
|  |  |- 染色法
|  |  |- 不存在奇环（长为奇数的环）
|  |- 二分图最大匹配（匈牙利算法）
|  |- 二分图最小点覆盖（König定理二分：二分图中，最小点覆盖=最大匹配）
|  |- 二分图最大独立集（二分图中，最大独立集=n-最小点覆盖）
|  |- 例题（关于建边）
|- 图的联通
|  |- 定义（只有概念，详细定义见下）
|  |  |- 无向图中的定义
|  |  |  |- 连通图
|  |  |  |- 子图
|  |  |  |- 连通子图
|  |  |  |- 连通分量（最大联通子图）
|  |  |- 有向图中的定义
|  |  |  |- 强连通图
|  |  |  |- 强连通子图
|  |  |  |- 强连通分量
|  |  |  |- k连通图（双连通图）
|  |  |  |- 割点
|  |  |  |- 桥
|  |  |  |- 双连通分量
|  |  |  |- 点双连通分量
|  |  |  |- 边双连通分量
|  |- 算法
|  |  |- 如何求强连通分量（SCC）= 如何缩点
|  |  |  |- Kosaraju算法
|  |  |  |- Tarjan算法
|  |  |  |- Gabow算法（略）
|  |  |- 如何求桥/割点
|  |  |  |- Tarjan算法（对还是它）
|  |  |- 如何求点/边双连通分量
|  |  |  |- Tarjan算法（啊？）

学习内容的模板（以及图论常用模板）

二分图最大匹配（König算法）

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<int> g[MAXN];
bool vis[MAXM];
int lst[MAXM];

bool konig(int u) {
	for (auto &v : g[u]) {  // auto好用的
		if (vis[v]) continue;
		vis[v] = 1;
		if (lst[v] == 0 || findargu(lst[v])) {
			lst[v] = u;
			return 1;
		}
	}
	return 0;
}

int main() {
    int cnt = 0;
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof vis);  // 打时间戳可以优化常数
		if (findargu(i)) cnt++;
	}
	cout << cnt;
}

强连通分量（SCC）以及缩点

例题（附带最短路）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], dfncnt;  // 两个关键数组：dfn, low
bool ins[MAXN];
int st[MAXN], top;  // 手写栈
int tag[MAXN], tagcnt;  // 标记数组，tagcnt是强连通分量的个数

void tarjan(int u) {
	dfn[u] = low[u] = ++dfncnt;
	ins[u] = 1;
	st[++top] = u;
	for (auto &v : g[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (ins[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		tagcnt++;
		while (1) {
			int v = st[top--];
			ins[v] = 0;
			tag[v] = tagcnt;
			if (v == u) break;
		}
	}
}

int main() {
    // 因为不确定图是否连通，所以对于每一个点都要跑一遍Tarjan
    for (int i = 1; i <= n; i++) {
		if (!dfn[i]) tarjan(i);
	}

    // 缩点(建新图)
    vector<int> h[MAXN];
    for (int i = 1; i <= m; i++) {
        if (tag[e[i].u] != tag[e[i].v]) {
            h[tag[e[i].u]].push_back(tag[e[i].v]);
        }
    }
}

割点

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], dfncnt;
int tag[MAXN], tagcnt;  // 求割点不需要使用栈

// 割点
bool cut[MAXN];  // 标记那些点是割点
int cnt;  // 统计割点个数
void tarjan(int u, int f) {
	dfn[u] = low[u] = ++dfncnt;
	int sons = 0;
	for (auto &v : g[u]) {
		if (!dfn[v]) {
			tarjan(v, u);
			sons++;
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u] && !cut[u] && u != rt) {  // 割点的判断-1
				cut[u] = 1;
				cnt++;
			}
		} else if (dfn[v] < dfn[u] && v != f) low[u] = min(low[u], dfn[v]);
	}
	if (u == rt && sons >= 2 && !cut[u]) {  // 割点的判断-2
		cut[u] = 1;
		cnt++;
	}
}

桥

例题（没有例题，不要点开）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], dfncnt;
int tag[MAXN], tagcnt;  // 求桥还是不需要使用栈

// 桥（输出到stdout）
void tarjan(int u, int f) {
	dfn[u] = low[u] = ++dfncnt;
	int sons = 0;
	for (auto &v : g[u]) {
		if (!dfn[v]) {
			tarjan(v, u);
			sons++;
			low[u] = min(low[u], low[v]);
			if (low[v] > dfn[u]) {  // 桥的判断
				cout << u << " " << v << endl;
			}
		} else if (dfn[v] < dfn[u] && v != f) low[u] = min(low[u], dfn[v]);
	}
}

点双连通分量

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int dfn[MAXN], low[MAXN], dfncnt;
int tag[MAXN], tagcnt;
stack<int> st;
int rt;
vector<int> ans[MAXN];
int cnt;

void tarjan(int u) {
	dfn[u] = low[u] = ++dfncnt;
	st.push(u);
	if (u == rt && !head[u]) {  // 判断孤立点
		ans[++cnt].push_back(u);
		return ;
	}
	for (int i = head[u]; i; i = g[i].nxt) {  // 这里使用链式前向星
		int v = g[i].to;
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				cnt++;
				int p;
				do {
					p = st.top();
					st.pop();
					ans[cnt].push_back(p);
				} while (v != p);
				ans[cnt].push_back(u);
			}
		} else low[u] = min(low[u], dfn[v]);
	}
}

dijkstra算法

例题0 例题1 例题2 （例题0是板子，例题1-2是缩点+最短路）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 值得注意的一点是，dijkstra算法处理最长路时会损失效率（虽然可以卡过），所以在处理最长路时使用SPFA会更加有效（尽管它死了）
// 上述内容对应例题2，如果使用dijkstra算法的话会WA#3
struct node{
	int dis, u;
	bool operator < (const node& a) const {
		return dis > a.dis;
	}
};

bool vis[MAXN];
int dis[MAXN];
priority_queue<node> q;

void dijkstra(int s) {
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	q.push({0, s});
	while (!q.empty()) {
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto &i : h[u]) {
			int v = i.first, w = i.second;
			if (dis[v] > dis[u]+w) {
				dis[v] = dis[u]+w;
				q.push({dis[v], v});
			}
		}
	}
}

SPFA算法

例题0 例题1 （例题0是板子，例题1是缩点+最短路）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// SPFA尽管死了并且它的效率要比dijkstra慢，但是其拥有良好的负环检测系统，关键是：最长路能用
vector<int> h[500010];
int dis[500010], cnt[500010];
bool vis[500010];
queue<int> q;

// 这是最长路并且统计的是点权，改为最短路/统计边权只要参考dijhstra就好
bool spfa() {
	memset(dis, -1, sizeof dis);  // 最短路需改
	int f = tag[s];
	q.push(f);
	dis[f] = mon[f];
	vis[f] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (auto &i : h[u]) {
			if (dis[i] < dis[u]+mon[i]) {  // 最短路/统计边权需改
				dis[i] = dis[u]+mon[i];  // 最短路/统计边权需改
				cnt[i] = cnt[u]+1;
				if (cnt[i] >= tagcnt) return 0;
				if (!vis[i]) {
					q.push(i);
					vis[i] = 1;
				}
			}
		}
	}
	return 1;
}

学习内容——各种定义

强连通/连通图

在无向图中，任意两点都直接或间接连通，则称该图为 连通图(connected).

相应的，有向图中任意一点都存在路径到达任意另一点，则称该有向图为 强连通图(strong connected) .

子图

在一个图 $H$ 中，$H$ 的所有边属于图 $G$ 的所有边，$H$ 的所有点属于图 $G$ 的所有点，则称图 $H$ 是图 $G$ 的 子图(subgraph) .

连通分量

无向图 $G$ 的最大连通子图称为 $G$ 的 连通分量(connected components) .

何为最大连通子图？这个子图是 $G$ 的连通子图，将 $G$ 的任何一个不在这张子图中的点加入这张子图后，该子图不再连通.

强连通分量（SCC）

在任意有向图中能够实现强连通的部分我们称其为 **强连通分量(Strongly connected component)**，如下图，蓝色框内的分别是一个强连通分量.

https://www.z4a.net/images/2023/12/12/wikiimg.png

如果把每个强连通分量收缩为单个顶点，得到的是一个 **有向无环图(DAG)**，于是我们可以在这个图的基础上进行拓扑排序，详见此例题.

而求这个强连通分量，我们可以使用两个算法：Kosaraju算法，Tarjan算法.

Kosaraju算法的流程如下：

  1. 重复寻找图 $G$ 中未被讨论的点，从它开始DFS后序遍历图 $G$ ，遍历到的点置为已讨论，用数组记录每个点到达的先后次序，直到找不到没有讨论的点.
  2. 将图 $G$ 反向得到图 $G’$ ，重置所有点为未讨论.
  3. 一直从数组中未讨论的最后一个点出发，DFS后续遍历图 $G’$ ，DFS每完成一次，就说明找到了一个强连通分量，直到数组中没有未讨论的点.

这是Kosaraju算法的模板（之所以Kosaraju算法没有放在SCC的模板内，是因为这个算法相对于Tarjan算法少用很多）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
bool g[1001][1001];  // 这里使用的是邻接矩阵
bool vis[1001];
int lis[1001], cnt = 0;
int tag[1001], scc = 0;
bool ind[1001];

void dfs1(int u) {
	vis[u] = 1;
	for (int i = 1; i <= n; i++) {
		if (g[u][i] && !vis[i]) dfs1(i);
	}
	lis[++cnt] = u;
}

void dfs2(int u) {
	vis[u] = 1;
	tag[u] = scc;
	for (int i = 1; i <= n; i++) {
		if (g[i][u] && !vis[i]) dfs2(i);  // 这里注意，判断的边是g[i][u]，因为我们要在反图上跑dfs2()
	}
}

int main() {
	for (int i = 1; i <= n; i++) vis[i] = 0;  // 这里可以用memset
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) dfs1(i);
	}
	for (int i = 1; i <= n; i++) vis[i] = 0;
	for (int i = cnt; i >= 1; i--) {
		if (!vis[lis[i]]) {
			scc++;
			dfs2(lis[i]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if ((tag[i] != tag[j]) && g[i][j]) {
                // 此处为缩点
            }
		}
	}
}

接下来我们来说说Tarjan算法，这个算法相对于上个算法理解起来要困难些.

在Tarjan算法中，最为重要的两个数组是 dfn[] 和 low[] ， dfn[i] 记录的是编号为i的节点在DFS的整个过程的顺序，它会在第一次访问到 $i$ 节点时更改，此后将不会变化；low[i] 表示的是 i 与其之后遍历到的节点所能到达的节点中 dfn 最小的 dfn ，在初始化时 dfn[i]=low[i] .

Tarjan算法在运行时会生成一棵搜索树，但是我们知道，图!=树，因为图中有一些边会使得“树”有环，自然，在生成树后，有一些边会直接指向已遍历的节点，没遍历的节点会在下一步当作自己的孩子进行遍历，而指向已遍历节点的边就是导致“树”有环的罪魁祸首.按照定义，当发现有这种边的存在时，需要更新当前节点的 low[] 值，需要更新为 min(dfn[这些边指向的节点]) .而理所当然地，我们也要被孩子节点更新 low 值为 min(low[孩子节点]) .

现在我们聚焦某一个点 $i$，观察 dfn[i] 与 low[i] 的关系，以下是两种情况：

  1. dfn[i]>low[i] ，这说明 $i$ 或其子孙节点存在边连到 $i$ 上方的节点.
  2. dfn[i]=low[i] ，这说明 $i$ 以及其子孙节点无法连到 $i$ 上方的节点，那么这个点 $i$ 就是一个强连通分量在这颗搜索树的根.

但是，$i$ 的子孙节点有可能会组成另一个强连通分量，这意味着 $i$ 的子树的节点不一定和 $i$ 处在同一个强连通分量内，我们需要 栈 来解决这个问题.

现在，我们用一张图看一下 dfn[] 与 low[] 的关系。

https://www.z4a.net/images/2023/12/12/13c47f67d62e6e7e8.png

在这张图中，有 (3,4,5,6) ，7 ，8 ，1 ，2 这四个强连通块.

下图是Tarjan算法的运行过程.

https://www.z4a.net/images/2023/12/12/Tarjans_Algorithm_Animation.gif

因为SCC模板就是Tarjan算法，所以在这里不放代码.

二分图的最大匹配

何为二分图？二分图是一种特殊的无向图，它的顶点可以被分为两个互斥的独立集 $U$ 和 $V$ 的图，使得所有边都是连结一个 $U$ 中的点和一个 $V$ 中的点（如下图所示）.

https://www.z4a.net/images/2023/12/12/Biclique_K_3_5_bicolor.svg.png

何为匹配？一个图的匹配是这个图中一些边所形成的集合，满足任意集合中的两条边都没有公共顶点.

解决这个问题的算法之一是匈牙利算法.在了解这个算法之前，我们先要了解一下何为增广路（增广轨/交错轨）.

增广路：若 $P$ 是图 $G$ 中一条连通两个未匹配顶点的路径，并且已匹配和未匹配的边（也就是属匹配边集 $M$ 的边和不属 $M$ 的边）在 $P$ 上交替出现，则称 $P$ 为相对于 $M$ 的一条增广路径.

不难发现，如果我们把 $P$ 中原来属于 $M$ 边从 $M$ 中删除，把 $P$ 中原来不属于 $M$ 边加入到 $M$ 中，变化后得到的新的匹配 $M’$ 恰好比原匹配多一条边.

而匈牙利算法就是不断寻找增广路 $P$ ，通过取反操作得到更大的匹配 $M’$ 来代替 $M$ .

代码如模板所示.

割点

是无向连通图中一个顶点 $v$ , 如果删除它以及它关联的边后，得到的新图至少包含两个连通分量.

这里同样使用Tarjan算法.

思路和求SCC的Tarjan算法类似，这里直接给出结论：

一个顶点 $u$ 是割点，当且仅当满足条件 $1$ 或 $2$.

  1. $u$ 为树根，且 $u$ 有两棵及以上的子树（这很好理解吧）.
  2. $u$ 不为树根，且满足存在一条 $(u,v)$ 为树枝边使得 dfn[u] <= low[v] ，即 $u$ 有一个孩子无法到达 $u$ 以上的点.

代码如模板所示.

桥

是无向连通图中的一条边，如果删除它，得到的新图包含两个连通分量.

求桥和求割点差不多，可以直接从代码看出差别，而且判断条件的理解也和求割点差不多，此处不过多赘述.

双连通图

不含割点的无向连通图.

双连通分量

无向连通图的最大双连通子图.

点双连通分量

通过找割点获得的双连通分量（层层递进.jpg

边双连通分量 （模板没打）

通过找桥获得的双连通分量.

心得体会

主要是图论之前有接触过，所以理解概念会比较快，同时在这一周我把之前一直没弄懂的Tarjan算法搞懂了.

现在的问题主要是建边的技巧以及破题的能力，像这种题（[SDOI2010]所驼门王的宝藏），这些建边的技巧想不到.

图论的常识有些遗忘了，例如Dijkstra跑最长路不能保证时间复杂度这类东西.

关注我

链接

最新文章

归档

标签

乘法逆元1
二分图1
优化2
动态规划4
图论2
存储2
思想1
总结13
技巧1
排列组合1
数学2
数据结构1
最短路2
欧拉反演1
游记1
算法1
背包问题1
解题报告1
连通块1
随笔1
题解4
×