图论题解

发表于 2020-07-10 更新于 2021-06-17 分类于 OI 阅读次数：

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

[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)+2E$，其中$E$是没有被环边跨过的边集。当起点不为$1$时，考虑把和起点相交的环缩在一起。在走的过程中一定会经过边界，那么此时直接走到其它环进行上面的做法即可。当起点不为$1$时，可能起点被大环套在里面。那么走到大环上需要额外的代价。这个代价可以用最短路求出。

[SDOI2019] 世界地图

题意：给一个网格图，且特别的，网格图左右相连，上下不相连。每次给一个左右区间，求删掉后的MST。$n \leq 100, m \leq 10000$ 求一个前缀MST，求一个后缀MST，合并即可。问题就是如何维护MST。以前缀为例：加入一排点的时候，会影响之前的一些链。链满足两端点都在上一排点。所以维护一个MST的虚树就可以了。

[AGC017E] Jigsaw

题意：有条状拼图：中间有一条，左右各有悬空的一条。中间的高度给定。现在要把拼图横着放，满足没有块有左右悬空。判断是否可行。如果有悬空的，下一块必须不悬空。并且高度相同。定义拼图左右各有一个权值，取决于它是否悬空，以及它在左边还是右边。把左右权值连边。那么就是要找若干条边不交的路径，覆盖整个图，并且特别的，钦定了起点终点类型。考虑新建一个源点作为起点，路径就变成了回路。考虑入点，入度不能大于出度，出点出度不能大于入度。特别的，联通块必须存在入出度不等的点。这是因为如果不存在，那么只能对一个点加两条边，不合法。而只要存在一个点不等，就会存在另一个点对称的不等。

[ARC092D] Two Faced Edges

题意：有向图，对于每条边求改变方向后强连通分量数量是否改变可以发现问题等价于删掉这条边后，是否$x$可以到达$y$和$y$可以到达$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$的。可以发现就是上一次的数量乘一下，减去合并的数量。合并的数量取决于原图中竖着拼起来合并了多少。于是可以矩阵乘法。