0. 前置

图论基础内容
最短路
最小生成树，次小生成树
邻接矩阵存图，边表存图
差分约束
矩阵乘法，矩阵快速幂
二分图匹配
最小割定理
最大独立子集和最大团的转化
有向图强连通分量
边双连通分量
点双连通分量
缩点
2-SAT

1. 一类基于矩阵乘法的问题

我们记 (mathbf{A}_{x,y}) 表示矩阵 (mathbf A) 的第 (x) 行第 (y) 列的元素 .

先说一下此处邻接矩阵的定义（设邻接矩阵为 (mathbf G)）：

无权图邻接矩阵：若 (i o j) 有边，则 (mathbf G_{i,j}=1)，否则 (mathbf G_{i,j}=0) .
有权图邻接矩阵：若 (i o j) 有一条边权为 (w) 的边，则 (mathbf G_{i,j}=w)，否则 (mathbf G_{i,j}=infty) .

1. Problem 1

一个 (n) 个点 (m) 条边的无权图，求 (a) 到 (b) 经过 (t) 条边的路径数量 .

先考虑一张图的邻接矩阵 (mathbf G)，若 (t=1)，那么 (mathbf G_{a,b}) 即为答案 .

考虑 (mathbf G^2)，根据矩阵乘法的定义：

[mathbf G^2_{a,b}=sum_{i=1}^nmathbf G_{a,i}mathbf G_{i,b} ]

因为 (mathbf G) 的每个元素要么为 (0)，要么为 (1)，从而，当且仅当 (a o i)，(i o b) 都有边时，(mathbf G_{a,i}mathbf G_{i,b}) 才等于 (1) .

不难发现，当 (t=2) 时，答案恰好为 (mathbf G^2_{a,b}) .

我们再考虑 (mathbf G^3)：

[egin{aligned}mathbf G^3_{a,b}&=sum_{i=1}^nmathbf G_{a,i}mathbf G^2_{i,b}\&=sum_{i=1}^nmathbf G_{a,i}left(sum_{j=1}^nmathbf G_{i,j}mathbf G_{j,b} ight)\&=sum_{i=1}^nsum_{j=1}^nmathbf G_{a,i}mathbf G_{i,j}mathbf G_{j,b}end{aligned} ]

类似的，当且仅当 (a o i)，(i o j)，(j o b) 都有边时，(mathbf G_{a,i}mathbf G_{i,j}mathbf G_{j,b}) 才等于 (1) .

不难发现，当 (t=3) 时，答案恰好为 (mathbf G^3_{a,b}) .

一般的，是否有答案为 (mathbf G^k_{a,b})？

答案是肯定的，分析类似 .

重边自环问题不大 .

2. Problem 2

一个 (n) 个点 (m) 条边的图，求 (a) 到 (b) 经过 (t) 条边的最短路 .

这个问题和 Problem 1 非常相似，先考虑一个 dp 方法 .

令 (dp_{i,j}) 表示通过 (i) 条边到达 (j) 的方案数，则：

[dp_{i,j}=min_{i=1}^{k}(dp_{i-1,k}+mathbf G_{k,j}) ]

其中 (mathbf G) 是图的邻接矩阵 .

直接暴力 dp 肯定是得不到满分的，我们对 Problem 1 设计一个类似的 dp 算法（状态类似）：

[Dp_{i,j}=sum_{i=1}^kDp_{i-1,k}mathbf G_{k,j} ]

发现它们两个非常的相似，所以考虑定义一种新的「矩阵乘法」运算，我们定义两个矩阵 (mathbf A) 与 (mathbf B) 之间的「新矩阵乘法」为：

[(mathbf Acirc mathbf B)_{i,j}=min_{k=1}^b(mathbf A_{i,j}+mathbf B_{k,j}) ]

其中 (mathbf A) 是 (a imes b) 的矩阵，(mathbf B) 是 (b imes c) 的矩阵，(mathbf Acirc mathbf B) 是 (a imes c) 的矩阵 .

不难验证 (circ) 运算有结合律：

[egin{aligned}((mathbf Acirc mathbf B)circmathbf C)_{i,j}&=min_{l=1}^cleft(min_{k=1}^b(mathbf A_{i,k}+mathbf B_{k,l})+mathbf C_{l,j} ight)\&=min_{k=1}^bmin_{l=1}^c(mathbf A_{i,k}+mathbf B_{k,l}+mathbf C_{l,j})\&=min_{k=1}^bleft(mathbf A_{i,k}+min_{l=1}^c(mathbf B_{k,l}+mathbf C_{l,j}) ight)\&=(mathbf Acirc(mathbf Bcircmathbf C))_{i,j}end{aligned} ]

上矩阵快速幂，时间复杂度 (O(n^3log t)) .

类似题目

给定一张 (n) 个点 (m) 条边的图，求边数恰好为 (k) 的路径上最大边最小是多少 .
定义：

[mathbf Acirc mathbf B=min_{i=1}^nmax{mathbf A_{i,k}mathbf B_{k,j}} ]

给定一张 (n) 个点 (m) 条边的图，求边数恰好为 (k) 的路径上最大边最小是多少 .
同理
给定一张 (n) 个点 (m) 条边的图，求边数不超过 (k) 的路径上最大边最小是多少 .
对每个点 (u) 都连一条 (u o u) 边权为 (-infty) 即可 .
给定一张 (n) 个点 (m) 条边的图，求边数在 ([k_1,k_2]) 的路径上最大边最小是多少 .
设原矩阵为 (mathbf G)，每个点 (u) 都连一条 (u o u) 边权为 (-infty) 之后的矩阵是 (mathbf G) .
观察矩阵乘法 (circ) 的定义，可以发现答案就是 (mathbf G_0^{k_1}mathbf G^{k_2-k_1}) .

2. 一类二分图匹配问题

1. Problem 1

问能否通过交换方格图的某些行列，使得对角线上的数全部是 (1) .

把每个格子和其对应对角线点连边跑二分图匹配即可 .

2. Problem 2

(n imes m) 的方格图，若干地方有障碍，问最多能放多少个物体，使得这些物体彼此之间不能互相看见（物体有视力，物体的视线会被障碍挡住）

把不能看到的点连边，然后跑二分图匹配

3. Problem 3

(n) 男 (n) 女，给出哪些对可以跳舞，每次开始播放歌曲，某些对就会跳舞，跳舞之后，每个男如果存在一个没有跳舞的女且能够跳舞，他就会找该女更换舞伴
现在希望：至少有一对人跳舞并且跳舞后没有人愿意改变舞伴
输出任意一种方案

当全部匹配或者一人匹配失败时答案就出来了 .

杂题

咕