CSP 2019 集训 图论

图论

NOIP 欢乐 赛

和

注意到模意义下有乘法群，因此 $n$ 的范围可以放到 $m$。

如果直接暴力当然是可以拿到 80 分，但是带个 $\log 10^{18}$ 肯定不能过 $3\times 10^6$。

于是这里有一个把指数变小的小优化——扩展欧拉定理。

a^{b}\equiv \begin{cases}\begin{align} &a^{b\% \varphi (p)}, & a\perp p \\ &a^{b},&\gcd(a,p)>1,b<\varphi(p)\\ &a^{b\%\varphi(p)+\varphi(p)},&\gcd(a,p)>1,b\ge \varphi(p) \end{align}\end{cases}

总之就是如果 $b\ge\varphi(p)$，$a^b\equiv a^{b\% \varphi (p)+\varphi (p)}$。

为什么呢？

证明有一定的难度，就先咕咕。可以参考这篇文章。

可是 $\log k$ 和 $\log m$ 其实差距不大。因此该 T 还是 T。

怎么办呢？

考虑我们是怎么计算 $\varphi,\mu$ 这些函数的？它们是积性函数，因此我们可以用线性筛计算。

这里也是一样。我们对于每一个质数调用线性筛计算 $p^b$，对于合数直接根据已经算好的 $p^b$ 得到 $a^b$。这样的时间复杂度就是 $O(n+\log n\log m)$，可以通过本题。

三角形

三元环计数题啊……

正统的三元环计数方法是由度数大的点向度数小的点连边（反之亦可，度数相等的点按编号顺序）。然后对于每一个点 $x$，标记它所有（出边的）邻点 $u$，标记完成后再从每一个邻点 $u$ 遍历它的所有邻点 $v$，如果 $v$ 也是 $u$ 的邻点（也就是被 $u$ 标记过），那么就找到了一个三元环。

关于时间复杂度，考虑把上面两步（从 $x$ 出发的遍历和从 $u$ 出发的便利）分开计算。第一步的时间复杂度是 $O(n+m)$，第二步则比较玄学，是 $O(n\sqrt{m})$ 一类的（假设 $n,m$ 同阶）。

如何计算补图中三角形的数目呢？

考虑原图中的所有三点组，这些三点组之间可能有 $0,1,2,3$ 条边。并且式子 $m(n-2)$ 就把所有的一边组计数 $1$ 次、二边组计数 $2$ 次、三边组计数 $3$ 次。在上述找三元环的过程中很容易计算出一边组和三边组的数量，再算出二边组的数量，用总的三点组数减去一、二、三边组的数量就可以得到补图中的三元环数了。

这种题……如果不知道算法的话就多多暴力吧。

数

谁知道这题暴搜能过啊？

最短路

Greg and Graph

所有的删东西都是不好做的，因此只要题目允许，直接离线倒过来做。

加点？$n\le 500$？直接 Floyd 就可以了。

如果要加边，似乎是 SPFA？虽然正解似乎是动态树就是了。

社交网络

$n\le 100$ 的最短路？直接 Floyd 更新一下方案数。

权值变换

$f(x)=-\frac{1}{x-1},\ f(f(x))=1-\frac{1}{x}$。好像没有什么希望？

再算下去就可以了，$f(f(f(x)))=x$！

由于三次就循环了，所以只需要扩充状态，记录当前走的步数模 $3$ 即可。

欧拉路和欧拉回路

SGU101

这道题怎么好像是见过的样子……？

如果把骨牌当做点，相同的数字当做边，然后……边数怎么好像很大的样子？而且我们要求的是一条恰好所有点且不重复的路径，这是……哈密顿路径？NPC 啊。

这里有更好的方法！

把数字当做点，骨牌当做边，就变成欧拉路径了。

POI Garbage

这里有一个神奇的地方，存在一种方案，使得每一条边都只被操作奇数次，因为考虑两个有交的操作环（桥环），他们的公共边会被操作两次；但是如果我们观察实际操作一次的边，就会发现这些边是两个环的异或，并且恰好形成了一个大环；于是这样的操作可以被替换为“操作一个大环”。

DAG

经典题

求 DAG 上 $1$ 到 $n$ 路径的必经点。

考虑路径计数，如果 $1\rightarrow u$ 的路径数和 $u\rightarrow n$ 的路径数之积等于 $1\rightarrow n$ 的路径数，就说明 $u$ 是必经点。

菜肴制作

求（置换群意义下）逆元的字典序最小的拓扑序。也就是在 $1$ 的位置尽量靠前的前提下，让 $2$ 的位置尽量靠前；……；在 $1,2,\cdots,k$ 的位置尽量靠前的前提下，让 $k+1$ 的位置尽量靠前；……

事实上这里有一个很巧妙的转化：取反图，在反图上跑字典序最大的拓扑序，再反过来就可以了。

这怎么证明呢？其实相当有难度。

先证明一个小引理：反图的任意拓扑序反过来都是原图的拓扑序。这个根据拓扑序的定义就可以证出来了。

下面说明这个算法一定会计算出最优解（证明不会证）。在反图上求解的过程中，如果在当前所有可选点中尽量选择大的，那么可以把小的位置留给小的点，并且可选的点的集合会变大；因此从理解上，这样是最优解。

连通性

Business

这是入门经典的题目。我们肯定不会选择割点，接着讨论每一个点双，如果点双的周围有不小于 $2$ 个割点，那么久不需要选；如果只有 $1$ 个割点，那么就要在连通块内部建一个。特别地，如果全图点双连通，需要选 $2$ 个。

也可以从缩点的角度考虑。

新年的毒瘤

根据树的定义——树是 $n$ 个点、$n-1$ 条边的简单无向连通图；因此只要删除一个点后，图仍满足这个性质，那么这个点就是毒瘤节点。只需要考虑非割点的点，去掉之后边数是否符合条件即可。

CF402E Strictly Positive Matrix

这题真的很厉害。

首先由于我们只关心是不是 $0$，因此我们可以把所有的正数变成 $1$，这样这个矩阵就变成了 $01$ 矩阵。

接下来根据讲课内容，我们要把这个矩阵与图论联系起来。图论……矩阵……

似乎只有邻接矩阵和基尔霍夫矩阵了。那么邻接矩阵的 $k$ 次幂是什么意思呢？

先令 $k=2$。那么 $G^2_{i,j}=\sum \limits_{u=1}^{n} G_{i,u}\times G_{u,j}$，由于只关心 $01$，又可以化为 G^2_{i,j}=\bigcup\limits_{u=1}^{n} G_{i,u}\and G_{u,j}。发现了什么？和 Floyd 很像吧。这就表示 $i$ 能否途经 $u$ 到达 $j$！

于是问题就明朗了。$G^k_{i,j}$ 表示是否存在长度为 $k$ 的 $i\rightarrow j$ 路径。因此只要这个图是强连通的，就可以满足要求。由于 $n$ 只有 $2000$，因此每个点搜一遍就好了。

另外多提一句，如果不改为 $01$ 矩阵，这个 $G^k$ 又是什么意思呢？

邻接矩阵某一位上的数如果大于 $1$，就说明这两点间有重边。而再看 $G^2_{i,j}=\sum \limits_{u=1}^{n} G_{i,u}\times G_{u,j}$，就会发现…… $G^{2}_{i,j}$ 表示长度为 $2$ 的 $i\rightarrow j$ 路径的条数！于是 $G^{k}_{i,j}$ 就表示长度为 $k$ 的 $i\rightarrow j$ 路径的条数。