10-04 图论杂题 笔记

今天讲课的内容还是比较和蔼可亲的,听课体验较好.除了最后一道神仙题(没放上来)之外其他的题都比较可做,不是太难.

「CF1037D」

Description

一个 $n$ 个点 $m$ 条边的无向连通图从 $1$ 号点开始 $bfs$,可能得到的 $bfs$ 序有很多,取决于出边的访问顺序。

现在给出一个 $1$ 到 $n$ 的排列,判断是否可能是一个 $bfs$ 序。

$n, m \le 2 * 10^5$

Solution

一个巧妙的做法:

对于每个节点,令其权值为在给定序列中的位置。

然后从 $1$ 号点开始正常的 $bfs$,出边的访问顺序按照权值从小到大访问。

最后将得到的 $bfs$ 序与给定序列比较,若完全一致则是合法的。

也就是说假定给定的$bfs$是合法的,按照这个来$bfs$再验证

「CF901D」

Description

一个 $n$个点 $m$ 条边的无向连通图中每个点都有一个权值

现在要求给每条边定一个权值,满足每个点的权值等于所有相连的边权之和,权值可负。

Solution

这道题和「CF990F」Flow Control - 构造有点像,但是还是有细微差别

先随便构造一棵生成树跑一遍,但这时根节点可能还不满足条件

考虑其他的边,一条非树边会形成一个环。

• 如果是偶环,那么无论这条非树边怎么变,都不会对根节点产生影响。
• 如果是奇环,那么如果给这条非树边增加或减少权值,根节点会发生 $2$ 的权值变 化,具体是加还是减由路径长度奇偶性决定

「CF894E」

Description

给定一个 $n$ 个点 $m$ 条边的有向带权图,对于一条边权为 $w$ 的边,经过时将获得 $w$的收益,之后$w=\lfloor \frac{w}{2}\rfloor$

请问从 $1$ 号点出发随便走最多能获得多少收益。

Solution

一个强连通分量内部所有的边肯定可以被走到底。

所以缩点后 dp 就行了

「CF859E」

Description

有 $m$ 个人,$n$ 张椅子,第 $i$ 个人只能坐在第 $u_i$ 或第$v_i$ 张椅子上。

求有多少种方案满足没有人坐在同一张椅子上。

Solution

这种题有点套路啊...

把椅子作为点,人作为边,变成一个图,每个连通块可以分开考虑。

假设某个连通块中有 $v$ 个点,$e$ 条边,由于连通,有 $v - 1 \le e$,并且若 $e > v$ 则无解,所以 $e$ 只有 $v - 1$ 和 $v$ 两种取值。

• 假如 $e = v - 1$,那么该连通块有 $v$ 种方案:考虑枚举每个点不放的情况,其他的点都可以唯一确定。
• 假如 $e = v$ 且环长 $> 1$,那么该连通块有 $2$ 种方案:考虑环上的一条边,这条边的放法确定后其他的都可以唯一确定。

「CF852D」

Description

给定一个 $v$ 个点 $e$ 条边的带权无向图,在图上有 $n$ 个人,第 $i$ 个人位于点 $x_i$ ,一个人通过一条边需要花费这条边的边权的时间。现在每个人可以自由地走。求最短多少时间后满足结束后有人的节点数 $\ge m$ $n, v \le 500$

Solution

先$floyd$ 预处理出两两之间的距离。

然后可以二分答案。二分答案之后,每个人向能走到的点连边。

可以发现合法的条件就是最大匹配数 $\ge m$,跑二分图匹配就可以了。

「CF850D」

Description

一个竞赛图的度数集合是由该竞赛图中每个点的出度所构成的集合。

现给定一个 $m$ 个元素的集合,第 $i$ 个元素是 $a_i$ 判断其是否是一个竞赛图的度数集合,如果是,找到点数最小的满足条件的竞赛图。

$m, a_i \le 30,a_i$ 互不相同

Solution

首先给出结论:

假如给出每个点的出度,那么这些点能形成一个竞赛图当且仅当排序后的序列 $d_1 , d_2 , d_3 , ... , d_n$ 满足对于所有 $k < n$ 有 $\sum_{i=1}^kd_i \ge \frac{k\cdot (k-1)}{2}$且$\sum_{i=1}^nd_i=\frac{n\cdot (n-1)}{2}$

证明很简单,对于竞赛图的任意点集 $S$,都必须满足$\sum_{i\in S}d_i\ge \frac{|S|\cdot (|S|-1)}{2}$

(因为对于竞赛图的一个部分,它其中的点肯定两两有连边,并且这中间的点还有连出去的边,所以是大于等于)

所以 $n$ 的大小是 $O(max(a_i ))$ 级别的。

那么就可以 $dp$ 了,先将给定集合中的元素从小到大排序,便于剪枝。

设 $f[i][j][sum]$ 表示考虑完前 $i$ 个元素,当前图中已经有$j$ 个点了,度数之和为$sum$转移时枚举下一个元素出现了几次就行了。

「CF845G」

Description

给定一个 $n$ 个点 $m$ 条边的带权无向连通图。

从 $1$ 号点出发,初始花费是 $0$,每经过一条边花费就会异或上这条边的权值,当你到达 $n$ 号点时可以选择停下来。

求停下来时的最小花费。

$n, m \le 10 ^5$

Solution

这道题前半部分还是很巧妙的,只可惜还不会线性基,只是大概了解,也暂时不打算学

假设 $s$ 和 $t$是两条 $1$ 到 $n$ 的路径,$C$ 是图中所有环的集合。那么 $t$ 的权值一定可以通过 $s$ 的权值异或上 $C$ 中一些环的权值来得到。

那先随便搞一棵生成树,然后对于每条非树边,都形成了一个环,这些环构成的集合是 $D$

那么 $C$ 中的每个环的权值都可以通过 $F$ 中的一些环的权值异或和来得到。

于是只要求出 $D$ 的线性基,然后随便搞一条路径在线性基上跑一下。

T8

算了...