图论题解

人比较菜,找的题也垃圾,轻点喷

[GYM102114A] Always Online

题意:仙人掌,求最大流异或和。

考虑环,那么注意到如果选环,环上最小的边一定会被割,直接把它割开,边权加在其它边上。之后按边权合并即可

[CF1240F] Football

题意:给一张图,选一些边,为每条边分配一个[1,k]的值,使得对于每个点的出边,值的出现次数极差\leq 2。构造解,最大化\sum w_i deg_i

枚举每一条边,考虑染色:如果有可用的方法,就直接染上。否则考虑对原图进行修改。考虑什么时候加不上新边。可以把一个点出边出现次数化为0,1,2。如果不存在可行边,要求不存在颜色在两边出现次数都< 2。考虑选择颜色A,在x出现2次,在y出现0次。B同理。

之后选x,y中的一个点为起点,走一条BA交错的路。之后把它反转。可以发现这样的路一定可以找到,并且反转后,一定可以加入新边。

[LibreOJ β Round #7] 网格图

题意:网格图内有K个障碍,钦定起点,多次询问到终点的距离。其中距离指转向次数。

首先把没用的缩起来:如果多行没有障碍,缩成一行。之后再把连续无障碍的段缩在一起,点数就是O(K)了。考虑优化边数:以行向列连边为例,考虑对于每一行,维护一棵线段树。那么连边就变成了区间连边。

具体来说,因为如果横着的是连续的,那么跨过它的一定也连续,所以主席树优化即可。之后BFS就可以了。

[JOISC 2016 Day 3] 电报

题意:给一张图,每个点的出度均为1。每个点有代价c_i,表示改变它出边指向的代价。最小代价使图变强连通

考虑如何变为强连通:把图断成若干链,再拼起来。如果只有树,那么贪心留下每个点入边最大的就可以了。如果是环,继续这么做。但是可能选了一整个环。特判掉就好了。

[IOI2017] 古书

题意:给一个排列p,要把i位置的书运到p_i位置。从一个位置走到另一个位置的代价是|i-j|。任意时刻,手上可以拿最多一本书。可以拿起,放下,交换,取决于当前位置和自己有没有书。一开始有起点s,求最小代价。

先假设起点是1。把排列变成图。我们称答案的下界d(p)=\sum{|i-p_i|}

如果只有一个环,答案是d(p)。如果有两个环,则当它们不交时,答案是d(p)+2,否则是d(p)。推广一下,当有多个环,答案是d(p)+2|E|,其中E是没有被环边跨过的边集。

当起点不为1时,考虑把和起点相交的环缩在一起。在走的过程中一定会经过边界,那么此时直接走到其它环进行上面的做法即可。

当起点不为1时,可能起点被大环套在里面。那么走到大环上需要额外的代价。这个代价可以用最短路求出。

[SDOI2019] 世界地图

题意:给一个网格图,且特别的,网格图左右相连,上下不相连。每次给一个左右区间,求删掉后的MST。n \leq 100, m \leq 10000

求一个前缀MST,求一个后缀MST,合并即可。问题就是如何维护MST。以前缀为例:加入一排点的时候,会影响之前的一些链。链满足两端点都在上一排点。所以维护一个MST的虚树就可以了。

[AGC017E] Jigsaw

题意:有条状拼图:中间有一条,左右各有悬空的一条。中间的高度给定。现在要把拼图横着放,满足没有块有左右悬空。判断是否可行。

如果有悬空的,下一块必须不悬空。并且高度相同。定义拼图左右各有一个权值,取决于它是否悬空,以及它在左边还是右边。把左右权值连边。那么就是要找若干条边不交的路径,覆盖整个图,并且特别的,钦定了起点终点类型。

考虑新建一个源点作为起点,路径就变成了回路。考虑入点,入度不能大于出度,出点出度不能大于入度。

特别的,联通块必须存在入出度不等的点。这是因为如果不存在,那么只能对一个点加两条边,不合法。而只要存在一个点不等,就会存在另一个点对称的不等。

[ARC092D] Two Faced Edges

题意:有向图,对于每条边求改变方向后强连通分量数量是否改变

可以发现问题等价于删掉这条边后,是否x可以到达yy可以到达x恰有一个成立。考虑第一个问题怎么做。本质上不经过(x,y)就是不经过x点。于是删掉x点,枚举出点,求是否存在两条到y的路。考虑优化,y点直接从(x,y)经过一次,从任意一个点经过一次,也就是经过两次即可,所以任意点如果已经被经过两次就不用BFS了。

[AGC004F] Namori

题意:树或者基环树,可以选一条边,如果两端点颜色相同,同时变色。一开始是白色,求最小变成黑色的次数。

把树黑白染色,之后问题转化为把树上每种颜色取反。这样可以把操作看作swap相邻的颜色。

对于树,贪心的求出每条边需要被经过多少次即可。令两种颜色分别为1,-1,维护f_u表示子树和。如果根的值不为0无解

对于环,删掉一条边当作树先做一下

如果是偶环:这条边假设被走了x次,则考虑这条边的两端点到LCA的路径,一个+x,一个-x。如果直接用DFS树,那么只需对每个点的f排序,取中位数为x即可

如果是奇环:之前定义操作一条边是swap颜色,但是现在奇环上的边两端颜色相同,所以可以看作是同时把某种颜色数量+-2。这条路不可以用来当捷径,所以操作它是不优的。但是它可以改变根的值,所以如果无解可以改为有解。

[AGC003F] Fraction of Fractal

题意:给01矩阵。定义k级分型是k-1级分型中每个1的位置放一个k-1级分形得到的矩阵。求k级分型连通块数。K \leq 10^{18}

首先特判一下不连通的块。如果任意方向两个块都联通,最终图也是联通的。所以只剩下了在左右/上下联通的图。以竖着联通为例,那么可以有这样的推论:最终的图一定是多个竖着的联通条。操作一次会合并若干联通条。

考虑知道了i-1的答案,求i的。可以发现就是上一次的数量乘一下,减去合并的数量。合并的数量取决于原图中竖着拼起来合并了多少。于是可以矩阵乘法。

  1. 头像 cbio说道:

    orz

  2. 头像 cbio说道:

    好神 好难/kk

发表评论

电子邮件地址不会被公开。必填项已用 * 标注