10-04 图论杂题 笔记

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

「CF1037D」

Description

一个 nn 个点 mm 条边的无向连通图从 11 号点开始 bfsbfs,可能得到的 bfsbfs 序有很多,取决于出边的访问顺序。

现在给出一个 11nn 的排列,判断是否可能是一个 bfsbfs 序。

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

Solution

一个巧妙的做法:

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

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

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

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

「CF901D」

Description

一个 nn个点 mm 条边的无向连通图中每个点都有一个权值

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

Solution

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

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

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

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

「CF894E」

Description

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

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

Solution

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

所以缩点后 dp 就行了

「CF859E」

Description

mm 个人,nn 张椅子,第 ii 个人只能坐在第 uiu_i 或第viv_i 张椅子上。

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

Solution

这种题有点套路啊...

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

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

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

「CF852D」

Description

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

Solution

floydfloyd 预处理出两两之间的距离。

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

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

「CF850D」

Description

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

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

m,ai30,aim, a_i \le 30,a_i 互不相同

Solution

首先给出结论:

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

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

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

所以 nn 的大小是 O(max(ai))O(max(a_i )) 级别的。

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

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

「CF845G」

Description

给定一个 nn 个点 mm 条边的带权无向连通图。

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

求停下来时的最小花费。

n,m105n, m \le 10 ^5

Solution

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

假设 sstt是两条 11nn 的路径,CC 是图中所有环的集合。那么 tt 的权值一定可以通过 ss 的权值异或上 CC 中一些环的权值来得到。

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

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

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

T8

算了...

感谢你的赞赏!