图论笔记 24-01-30

---

应试

考试中，图论数据量都是$10^5$量级的，所以用邻接表。
数组的定义记住估算一下空间，对数组大小有概念。
二维int数组最大开到$5000\times5000$
万不得已不要定义在主函数内。
规范变量命名。

---

memset

STL::memset
头文件cstring
使用方法memset(地址, 数值, 长度)
将地址的每一个字节填充数值
最大值填充0x3F即可

---

多少条边

有向图：
$C^2_n=\frac{A^2_n}{A^2_2}=\frac{n\times(n-1)}{2}$
无向图：
$A^2_n=n\times(n-1)$

---

邻接矩阵

空间复杂度$O(n^2)$，全部遍历时间复杂度$O(n^2)$

---

邻接表

稀疏图用，常考常用。
每一个点接的点在对应点后练成一个链，vector或数组模拟。
遍历全图时间复杂度$O(m)$

---

Floyd

集合的传递性：
$若A>B，B>C，则A>C。$

最短路径 ：
$d[i][j]=min(d[i][j],d[i][k]+d[k][j])$

最大边最小（最小生成树）：
$d[i][j]=min(d[i][j],max(d[i][j],d[k][j]))$

---

堆

堆就是一棵完全二叉树，$n$个节点。

以小根堆为例，从上到下，从左到右编号，$a_i\le a_{2i}$，$a_i\le a_{2i+1}$，这个父亲节点小于左儿子，也小于右儿子。这一棵完全二叉树称为小根堆，最小值是$a_1$，查询时间复杂度$O(1)$。

每一次修改、插入或删除，变化以后还是满足小根堆。

上浮操作
先放在后面，不符合把儿子和父亲换一下，一层层检查交换，$a_i$与$a_{\frac{i}{2}}$比较。插入时间复杂度$O(\log n)$。修改同理。

下沉操作
删除就是把最后一个移到删除的数上，与下面的比较，不符合就交换。时间复杂度$O(\log n)$。

---

优先队列

STL::priority_queue

在一个长度为$n$的序列中，可以完成两个操作：
1.询问最大值最小值
2.插入一个数

m次操作，时间复杂度$O(m\log n)$

---

Dijkstra

单源最短路算法：只有一个源点作为起点。
暴力$O(n^2)$
堆优化$O(m\log m)$
不能有负边存在

源点$s$
最短路$d_i$
标记数组$v_i$
初始条件$d_1=0$，其余为$\infty$。

贪心思想
因为没有负边，所以已求点最短路不会再变化。
两个集合，已求点（白点）和未求点（蓝点）。

第一步：蓝点中找一个与白点距离最近的。
第二步：将这个点变为白点，用这个点更新蓝点距离。
$d_x+a_{x,y}$更新$d_y$，$x$为白点，$y$为蓝点。
第三步：重复，直到全部变成白点。

暴力代码

void dijkstra(int s) {
	memset(vis, 0, sizeof(vis));
	for (int i-1; i<=n; ++i) d[i]=INF;
	d[s]=0;
	for（int i=1; i<=n; ++i） {
		int x=-1, mn=INF; // x不设置初始值可能会RE
		for (int j=1; j<=n; ++j) {
			if (!vis[j] && d[j]<mn) mn=d[x=j];
		}
		if (x==-1) return; // 这一步可选，意味着图是断开的
		vis[x]=1;
		for (int j=1; j<=n; ++j) {
			if (!vis[j]) d[j]=min(d[j], d[x]+a[x][j]);
		}
	}
}

还有一种写法，一开始就把起点变成白点，并预处理好起点所连接的边，下一次$1$就不用找了。代码较为麻烦。

$d_i$也可以维护最大边和最短边。
最大边最小：$d_i=min(d_i,\ max(d_j,\ a_{j,i}))$
最小边最大：$d_i=max(d_i,\ min(d_j,\ a_{j,i}))$

源码

---

SPFA

它死了