题面：
要求把 \(1\sim n\) 排序，满足给定的所有条件，满足条件之后，编号越小要越靠前。（满足条件情况下，先让 1 最靠左，然后让 2 ……）
每个条件会给出两个数 \(a,b\)，表示 \(a\) 必须在 \(b\) 之前。
解答：
看起来很像拓扑排序。于是我们对于每个条件 \(a,b\)，从 \(a\) 向 \(b\) 连一条边。每一个点只有在入度为 0 时，才能被选。
但是我们发现，如果我们这么做，无法保证编号小的更靠前：因为如果同一时刻有多个入度为 0 的点，我们并不知道选哪一个可以让编号小的更靠前。
因此转变思路，在反图上面作拓扑排序，每次如果有多个入度 0 的点，一定选其中编号最大的。
这样得出来的序列，就是所求序列的翻转。
二分图匹配/网络最大流。
第一问：强连通分量缩点后，入度为 \(0\) 的点的个数。
第二问：缩点后，\(\max(\)入度 \(0\) 个数，出度 \(0\) 个数\()\)。
强连通分量缩点后，剩下一个 DAG。之后就很普通了。
树剖
最大流
dfn 序转换到线段树上。
见 \(k\le 50\)，大喜，遂打表，以树上差分解之。
挖井可以看作和 \(0\) 连边。跑最小生成树。
一种搜索的想法是一个状态里包含四个数：\(bx,by,mx,my\) 为箱子和人的位置。
但这个状态是 \(O((nm)^2)\) 的，需要优化。
我们发现只关心箱子的步数，那能不能只存箱子的位置呢？这显然不行，因为我们要知道人往哪边推。
于是两种方案折中一下：当人推箱子的时候，人一定在箱子相邻的四个位置之一。而且我们不关心人走到另一边花多少步。
新的状态：\(x,y,dir\) 表示箱子位置 \((x,y)\) 且人在箱子的 \(dir\) 方向。（上下左右）
每次转移状态，枚举箱子下一次移动是朝哪边，同时再用一次 BFS 看一下现在人的位置能不能移动到枚举到的推箱子的位置，注意这个过程中不能经过箱子的位置。
时间复杂度是 \(O(n^2m^2)\) 的，数据比较水，卡一卡就能过。但是我们可以优化。
考虑时间复杂度的瓶颈其实在于每次看人能不能移动到另一个位置，这也需要 \(O(nm)\) 的复杂度。
我们把每一个格子抽象为一个结点，相邻的合法格子之间连边。问题就变成了 \(x,y\) 能不能在不经过 \(z\) 的情况下相互到达。（不经过 \(z\) 是因为不能经过箱子的位置）
可以通过分类讨论 \(x,y,z\) 的位置判断。可以参考这里。
题意：给图增加一些边，使得图内没有割边。
答案：割边个数 \(\div \,2\) 上取整。
证明：对图进行边双连通分量缩点，得到一颗树。设这棵树有 \(x\) 个点的度为 \(1\)，显然至少需要增加 \(x\div2\) 上取整这么多条边。
而发现如果把这些度为 \(1\) 的点都连通了，整个图也就没有割边了。
Kruskal 分阶段进行，如果一条边想加入的时候，发现比他小的边构成的连通块，已经使他的两端连通了，说明这条边一定不选。
把剩下可能选的边构成一张图，这张图里面的割边就是必选的边。
删掉一条边，让原图变成二分图，求方案数。
先把图里面所有连通分量找出来，如果这些连通分量中有至少两个不是二分图，方案数为 \(0\)。
如果全部都是二分图，方案数为 \(m\)。
剩下的情况我们就在那个不是二分图的连通分量里删边了。
考虑二分图的判定条件，一般就两种：可以二染色，没有奇环。
但是如果想判定二染色，需要 DFS 一遍，看起来不太行。考虑判断删掉一条边之后，要破坏所有奇环。
用一个图论经常使用的 trick：取 DFS 树。
因为是无向图，所以非树边只会是回边。
如果删一条回边使得奇环没了，显然必须要求图中只有一个奇环。剩下讨论删一条树边的情况。
下面定义：一条回边加若干树边形成的奇环称为错环，一条回边加若干树边形成的偶环称为对环。
因为要破坏所有错环，所以有一个 simple 的想法：取所有错环的树边的交集。这个交集的大小就是答案。
但是这个想法是错的。比如: 1-2-3-4 且 1-3, 1-4。上面的方法会输出 2。
观察这个算法为什么会错误：如果一个错环 + 一个对环，就会诞生一个奇环。
猜结论：如果一条树边不在任何一个对环，且在所有错环里，就可以。
（注意：我们这里不直接说奇环，而是分成对错环的原因是，对错环一定只有一条回边，但是奇环可能横跨多条回边。）
证明：这个命题其实有两个方向。
先证明：如果一条树边在所有错环，且在至少一个对环里，删了这条边不能让图变成二分图。
考虑一个错环 \(c_1\) 和一个对环 \(c_2\) 的异或。（图的异或：如果一条边恰好在一个图里存在，就保留；否则不保留。）
记这个异或为 \(c\)。显然 \(c\) 的边数是奇数，因为 \(c_1,c_2\) 的边数一奇一偶。
而考虑两个环的异或，发现这个异或一定可以把所有边划分成若干个环。
所以一定有一个奇环，所以一定不能让图变成二分图。
再证明：如果一条树边在所有错环，且不在任何对环里，删了这条边就行。
把这个图二染色。不管是否二分图。
记这条树边是 \(e\)，如果不看回边，这条树边会把所有点分成两个连通块。
我们把其中一个连通块所有颜色取反，就构造出一种二染色的方法。（取反的 trick 也经常用）
证毕。
有了这个结论，我们只需要判断一条边是否在所有错环且不在任何对环就行了。（时刻注意错环的奇环的定义差别）
可以对每一条非树边用树上差分。但是如果求 LCA 会带一个 \(O(\log n)\)。我们发现其实每一条非树边都是回边，所以这条非树边一定有一端是另一端的祖先。于是求 LCA 其实是 \(O(1)\) 的。
于是我们就做完这题了。
整理一下思路：
-
读入。
-
对每一个连通块二染色。
-
枚举每一条边，看一下是否有 \(\ge 2\) 个连通块不是二分图。如果有，答案为 \(0\)；如果所有连通块都是二分图，删掉任意一条边都可以；否则选定这个不是二分图的连通块的根。
-
一次 DFS。对每条回边，判断一下是对边还是错边，在对应的差分数组上加减；对每条树边，记录一下到达这个儿子走的边的编号，同时在递归进入儿子之后，让当前结点的差分数组累加上儿子的。
注意这里直接累加儿子的差分数组是正确的，同时可以大幅简化代码。
注意为了保证每条边只会统计一次，在每条边上要记录一个 \(val\)，在走过这条边的时候把这条边的反向的 \(val\) 改成 \(0\)。（和求割边的 \(val\) 一个意思）
-
枚举这个连通块内的每一条边，看一下它两端的差分数组是否满足在所有错环且不在任何对环内。把所有满足边的加入答案数组。
-
如果错边只有一条，把这条错边加入答案数组。
-
输出，注意输出的编号要从小到大排序。
思路：\(dp[i]\) 表示前 \(i\) 天的最小花费。
\(dp[i]=\displaystyle\min_{j=1}^{i-1}\{dp[j]+cost(j+1,i)\times (i-j+1)+k\}\)
其中 \(cost(j+1,i)\) 是指第 \(j+1\sim i\) 天都能使用的最短路长度。
数据范围很小，预处理随便跑。跑完预处理随便 DP 就行了。
难点是想到 DP。
删除两条边，使得图不连通，求方案数。\(1\le n\le 2000,1\le m\le 10^5.\)
先把割边这种简单情况拎出来解决了。
① 选两条割边，有 \(C_{cut}^2\) 种方法，\(cut\) 是割边条数。
② 选一条割边 + 一条非割边，有 \(cut\times(n-cut)\) 种方法。
③ 选两条非割边。下面解决这种情况。
因为现在已经和割边没有关系了，所以可以把每条割边连接的两个点合并成一个点。此时图里面就没有割边了。
经典 trick：DFS 树。
显然两条回边没办法不连通。
① 一条回边 + 一条树边。可以用一个 \(tot\) 数组统计跨越一条边的回边有多少条。
② 两条树边。我们发现，这两条树边一定有一条是另一条的祖先！如果它们是左右结构，因为没有割边，所以图依然会连通。
这时候我们的问题就变成：找两条有祖先关系的树边，使得图不连通。
记更浅的那条边为 \(e\)，更深的那条边为 \(e'\)。
进一步分析，我们发现：记跨越 \(e\) 的回边边集为 \(S_e\)，跨越 \(e'\) 的回边边集为 \(S_{e'}\)。 \(e,e'\) 可以让图不连通的充要条件是 \(S_e=S_{e'}\)。
也就是说，所有跨越 \(e\) 的，都要跨越 \(e'\)。所有跨越 \(e'\) 的，都要跨越 \(e\)。
假设此时所有跨越 \(e\) 的已经都跨越 \(e'\) 了。那这个时候有 \(S_e\subseteq S_{e'}\)，那我们只需要再来一个 \(|S_e|=|S_{e'}|\) 就行。而 \(|S_e|=|S_{e'}|\) 的判断可以用上面的 \(tot\) 数组完成。
现在的问题又变成了对于一个固定的 \(e\)，怎么找到所有 \(e'\) 使得所有跨越 \(e\) 的边都跨越了 \(e'\)。因为 \(1\le n\le 2000\)，所以树边条数 \(\le 2000\)，我们可以直接枚举两条树边。
这时我们只需要判断跨越 \(e\) 的边是否跨越了 \(e'\) 即可。有一个想法就是对每一个点记录一个属性 \(high\)：从这个点的子树里走，要走到这个点或者这个点上方，最深能走到多深。（一开始就在这个点不算）
如果我们求出了这个 \(high\)，要判断是否跨越，直接看一下 \(e\) 更深一端的 \(high\) 和 \(e'\) 更深一端谁更深就行了。
那怎么求 \(high\) 呢？有一种错误的想法是和求 \(low\) 类似求，但是这是错的。原因是当结点往浅走，子孙的 \(high\) 可能不再合法，但是又找不到次浅的。
我们可以用并查集做。先把所有回边按照靠上的点的深度从深到浅排序。显然一条回边会把 这条回边两端路径上 所有还没被赋值的点的答案 赋值为 这条回边较靠上的点。
可以用并查集，类似 People are leaving，把所有相连的答案被赋值的点合并到一起。每次枚举回边路径上的点，可以利用并查集跳过连续的被赋值的点。
但是，如果用按秩合并好像会导致代表元素不是最浅的点？
没关系，可以用一个额外的数组记录每一个连通块内最浅的点是哪个。
给定一张连通无向图，两点之间的距离若为奇数，称为奇对；偶对类似定义。（距离：简单路径长度，若距离可奇可偶，啥也不算）
注：关于简单路径的问题，尝试先想没割点的，再想圆方树。
先考虑没有割点的情况（点-二连通）。
如果是二分图，很简单；而如果不是二分图，就说明有奇环，可以推出任意两个点之间的距离奇偶性都不确定。
如果有割点，考虑圆方树。（圆方树：把割点全部删除，剩下每一个连通块都是方点，每个割点都是圆点，每个圆点和对应的方点连边，得到一棵树）
观察到：如果一个方点内部不是点-二连通的，发现如果两个点在这个方点的两侧，这两个点的距离奇偶性也是不确定的。
所以每一个不是二连通的方点，会把圆方树切成若干个连通块。对这些连通块内部各自求答案累加即可。
给定一张图，修改某些边权，使得最小生成树和最大生成树费用相同。（其实就是每颗生成树费用相等）
先考虑简单情况：一个圈。
这种情况等价于要求环上每条边的边权相等。所以最优解就是找出出现次数最多的边权保持不动，其余的边都改成这个边权。
进一步：点二连通分量。
还是要猜所有生成树费用相等的等价条件。
显然每条边费用相等是一个充分的条件。那这是不是必要的呢？感觉好像是，尝试证明！
先从图里面取出一个环，显然这个环上所有边边权应该相同。
再考虑一个“耳朵”：从这个环上面长出去的一条路径。
发现无论是连着耳朵上两个点的边，或者连着原本的环上一个点还有耳朵上一个点的边，都能找到一个环。所以所有边边权相等。
于是证明了点二连通的情况。下面考虑圆方树。
每个方点内部边权相等。而如果一条边有圆点（割点），这条边显然不管在任何生成树里面都会选。
所以只需要把每个方点内部的边权都改成这个方点内部边权的众数即可。
给定无向图，计数三元组 \((s,c,f)\)：存在简单路径 \(s-\dots-c-\dots-f\)。
简单情况：点二连通。
任意三个都有解！（注意有顺序，是 \(A\) 不是 \(C\)）
证明的话，也是先从一个环说起，然后不停加耳朵，画画找路径。
进一步：圆方树。
分类讨论 \(s,c,f\) 所在方点/圆点，是否同节点等。讨论 \(c\) 是否是割点，可以用树形 DP 统计。
给定一张无向图，带点权。支持两个操作：1. 查询两点之间一条简单路径，使得经过的点的权值最小值最小。 2. 修改某点点权。
简单情况：图无环。（一棵树）
可以树剖。
进一步：点二连通。
可以对每一个环用一个 multiset 维护最小值。
再进一步：无向图。
考虑圆方树。还是对每一个方点用 multiset 维护最小值。
对于每一个方点，显然我们一定可以取到最小值，所以对于每一个点，只维护它内部的最小值，然后把它缩成一个点。
这样就变成树的问题了，回到树剖。
无向图，有两个人初始都在一号节点，你可以给两人分别设定一条路径，他们就会按照这个路径走。
有一个结点（不是 \(1\)）是陷阱结点，只要访问到这里，人就会停下来。
求一种安排顺序，使得无论如何，每个结点都被访问过。（访问就是到达结点）
结论：如果 A 的路径是 \(A_1\sim A_n,(A_1=1)\)，B 的路径是 \(B_1\sim B_n,(B_1=1)\)。则如果是可行的，必须满足 \(A_2\sim A_n\) 是 \(B_2\sim B_n\) 的 reverse。
证明：如果 \(B_n\) 不是 \(A_2\)，则我们在 \(A_2\) 设为陷阱，那 \(B_n\) 就访问不到。
那我们只需要满足，路径任意一个前缀都是点双连通的。
而这是一个等价条件：如果存在不是 \(1\) 的割点，就无解！
所以我们判断无解，只需要判断是否存在不是 \(1\) 的割点即可。然后我们就能从 \(1\) 出发，依次访问每一个分支。两个人的访问顺序相反就行。
看到周期，考虑拆点
把每一个博物馆 \(i\) 在第 \(j\) 天到达抽象为一个点 \((i,j)\)。如果第 \(j\) 天的博物馆 \(i\) 能到达第 \(k\) 天的博物馆 \(l\)，就从 \((i,j)\) 向 \((k,l)\) 连线。
显然一个强连通分量里的都可以取到，我们强连通缩点，一个点的权值定为这个点内部可以到多少个不同的博物馆。
然后就可以 DAG 最长路了。
但是有个问题：会不会 \((i,j)\) 和 \((i,j')\) 在不同的SCC里，导致重复计算？
不会，因为如果 \((i,j)->(i,j')\)，显然 \((i,j)->(i,j')->(i,j+d(j'-j))->(i,j)\)，所以 \((i,j')->(i,j)\)，所以 \((i,j),(i,j')\) 应该在同一个SCC内。
这题卡 vector，要用前向星；还卡栈空间，加了个 inline 就过了。
题意：找到边权和最小的最短路树。
普通最短路树：用 Dijkstra，每次取出来一个点进行松弛的时候，如果点 \(A\) 成功松弛点 \(B\)，记录 \(pre[B]=A\)。结束后 \(pre[x]\) 就是 \(x\) 的父节点。
边权最小最短路树：
-
成功松弛的情况有两种，一种是到达新的点的距离严格小于原本的，这种肯定必须更换 \(pre[]\)；另一种新距离相等，于是我们可以比较一下这一次的边权和原本的边权，保留更小的。
-
我们发现上面的比较边权其实没必要。因为最短路长度相等，\(pre[x]\) 比 \(now\) 更先被拿出来松弛 \(x\)，肯定是因为 \(1\rightarrow pre[x]<1\rightarrow now\)，所以 \(pre[x]\rightarrow x>now\rightarrow x\)。因此，如果最短距离相等，也可以直接替换。
一张图被称为毛毛虫，当且仅当有一条路径，使得每个点到路径上的距离 \(\le 1\)。一次操作可以合并两个相邻的结点，连接他们俩的边变成自环。（毛毛虫不能存在重边，但是可以自环）
先考虑环：显然要合并 \(n-1\) 次。
然后考虑边双：也需要合并 \(n-1\) 次。
于是边双缩点成树。显然找一条直径作为最终毛毛虫的路径。
求有多少个点不在任何一个奇环内。
关键结论：每个点双，要么全不在，要么全在。
有多少种方法把图分成一个独立集和一个团？（之间的边随意，不能全部是独立集或者全部是团）\(n\le 5000\)。
一个点，要么属于独立集，要么属于团。于是考虑用 2-sat 求解。
用 2-sat 求出一组解之后，我们还要求出解的个数。我们发现，新的解要么是从原解的一边，拿出一个点放到另一边去；要么是从原解的两边交换一对点。
如果是拿出一个点放到另一边：
-
团放到独立集。我们要求出团里面有多少个与独立集的不连边，同时注意要保证团的点个数 \(\ge 1\)。
-
独立集放到团。和上面同理。
如果是交换：
对于换到团的那个点：要么连接团里面所有点，要么只不连接和他交换的那个点。
对于换到独立集的那个点：要么不连接独立集里任何一个点，要么只连接和他交换的点。
枚举两个点判断即可。
排列最小割
（高五 Class 3）
题意：给定图，找出一个点的排列 \(v_1\sim v_n\) 使得 \(\sum \mathrm{mincut}(v_i,v_{i+1})\) 最大。
首先求出最小割树。（Gusfield 等价流树）定义两点之间的距离为它们树上路径边权的最小值。我们就是要找一个排列，使得 \(\sum dist(v_i,v_{i+1})\) 最大。
取出树上最小的边 \(e\)。我们要尽量少经过这条边。
观察：存在一个最优解 OPT，只经过 \(e\) 一次。若 \(a>b>c>d\) 且 \(a>b\) 和 \(c>d\) 都经过了 \(e\)，可以调整法证明。
于是可以递归的得出答案就是最小割树中所有边之和。
对每个结点维护：\(w[x]\)，表示如果 \(x\) 是白色， 以 \(x\) 为根的子树中 \(x\) 所在的白色连通块大小。\(b[x]\) 类似定义。
（只考虑黑变白，白变黑对称）
假设 \(u\) 黑变白，我们找到 \(v\)：\(v\) 是离 \(u\) 最近的祖先且 \(v\) 为白色。如果 \(u\) 所有祖先都是黑色，令 \(v\leftarrow rt\)。
然后我们让 \(fa[u]\sim v\) 的 \(b[]\) 都减去 \(b[u]\)，\(w[]\) 都加上 \(w[u]\)。
怎么找最近的白点？可以线段树维护区间内第一个 0。
可以树剖维护，\(O(n\log^2 n)\)。
小蓝书“异象石”。
很显然能看出是个边双缩点 + 树形 DP。
先缩点，统计每个大点内部有 \(V[i]\) 个点，\(E[i]\) 条边。并且统计每个点的子树内的边数 \(s[i]\)。
先考虑 \(dp[i]\) 表示 \(i\) 的子树内有多少种方法。但是这样不好转移：递归求完 \(dp[son]\) 之后，不同的子树之间会影响。
所以 \(dp[i][0]\) 表示 \(i\) 的子树内一个军营也没有的方案数，\(dp[i][1]\) 表示 \(i\) 的子树内至少有一个军营，且所有军营要通过看守的边与 \(i\) 连通的方案数。
显然 \(dp[i][0]=E[i]\times \prod(2\times dp[son][0])\)。这个 \(2\) 是通往子树的那条边。
\(dp[i][1]\) 怎么求？可以用类似树形背包，不停往 \(dp[i][1]\) 里增加子树的影响的方法求：
若当前要增加子节点 \(x\)：（注意 \(dp[i][1]\) 要求必须选）
-
\(i\) 的子树还没有：\(x\) 子树内必须选，\(dp[i][1]\leftarrow dp[i][0]\times dp[x][1]\)。
-
\(i\) 的子树内选了：则 \(x\) 选不选都可以。\(dp[i][1]\leftarrow dp[i][1]\times (2\times dp[x][0]+dp[x][1])\)。
因此 \(dp[i][1]=dp[i][0]\times dp[x][1]+dp[i][1]\times (2\times dp[x][0]+dp[x][1]).\)
注意是赋值运算，而且 \(dp[i][1]\) 和 \(dp[i][0]\) 要同步更新，且 \(dp[i][1]\) 更新要在 \(dp[i][0]\) 之前。
有几个观察：
-
当机器人在 \(u\) 时，电量必须 \(\ge\) 到达最近充电桩的距离。
-
假设当前在 \(u\)，从 \(u\) 走到最近的充电桩再走回来，点亮不会变差。
从每个充电桩跑最短路，设 \(d[x]\) 为 \(x\) 到最近的充电桩的距离。
因此我们只需要记录能到哪个点，只要能到，这个点的电量就可以变成 \(C-d[u]\)，而且最高也是 \(C-d[u]\)。
考虑从 \(u\) 成功走到 \(v\) 需要满足什么条件：\(C-d[u]-W_{u,v}\ge d[v]\)。
转换一下，\(d[u]+d[v]+W_{u,v}\le C\)。于是我们令新边权 \(W'_{u,v}=d[u]+d[v]+W_{u,v}\)，重新建立一张图 \(G'\)。
若 \(a\) 能走到 \(b\)，充要条件就是 \(G'\) 上有一条路径 \(a\rightarrow b\) 上边权最大值 \(\le\) 初始电量。
因此我们就是要最大边权最小，可以对 \(G'\) 求 MST。
长链剖分原理。
\(dp[u][x]\) 表示 \(u\) 的子树内切若干次，且 \(u\) 能到达的最深的结点深度为 \(x\) 的方案数。
以合并子节点影响的方式计算。当前在合并 \(v\)。
-
不割 \((u,v)\)，\(dp[u][\max(p,q+1)]\leftarrow dp[u][p]\times dp[v][q],(p+q+1\le k)\).
-
割 \((u,v)\)，\(dp[u][x]\leftarrow dp[u][x]\times dp[v][p],(p,x\le k)\).
注意转移之间会有影响，用临时数组记录。
暴力做是 \(O(nk^2)\) 的，但是长链剖分优化 \(O(nk)\)。
可以二分答案 \(x\)。
对于边权大于 \(x\) 的，我们保留它们，然后 topo 判环。
在 topo 判环的过程中，可以求出每个结点的 topo 序。对于边权 \(\le x\) 的，如果是从 topo 序大的指向小的，就要改变。
ABC277H
自己点进去看题意。
巧妙转化：因为 \(nm\le 10^6\)，可以用 \(m\) 个布尔型变量表示一个变量：\(v_{i,j}=true\) 表示 \(x_i\ge j\)。
于是这题就可以转化为 2-sat 问题。（需要注意 \(v_{i,0}\) 必须为 \(true\) 和 \(v_{i,m+1}\) 必须为 \(false\)，这可以通过 \(v_{i,0}\) 向 \(v_{i,1}\) 连边这种方式来解决）
如果 \(d=0\)，裸的 2-sat。但是如果 \(d\neq 0\)，\(O((n+m)\times 3^d)\) 跑不过去。
我们其实只需要枚举 x 的位置为 a 或者 b，就能覆盖所有情况了。所以是 \(O((n+m)\times 2^d)\)。
题意：给定无权无向连通图，每个点有颜色。颜色种数 \(k\)。求出从每一点出发，要经过至少 \(s\) 种不同的颜色，至少经过多少条边。（\(n,m\le 10^5,s\le k\le 100\)）
对每一种颜色建立一个超级源点。依次从 \(k\) 个超级源点 BFS，可以求出每个点到每一种颜色的最短路。对于每一个点，将最短路距离排序，取前 \(s\) 小即可。
题意：判断一张无向图是否是 k-花。k-花：中间一个长度 \(k\) 的简单环，环上每个点又带出一个长度 \(k\) 的环。
满足以下条件的，就是 k-花：
-
有 \(k^2\) 个结点和 \(k^2+k\) 条边。
-
每个节点的度只能是 \(2\) 或 \(4\)。
-
连通。
-
切断所有连接两个度为 \(4\) 的节点的边后，恰好剩下 \(k\) 个长度为 \(k\) 的环。
前三个很好判断，第四个条件只需要枚举所有边，暴力从 vector 里删除即可。
注：从 vector 里删除，可以先遍历所有元素，如果遇到要删除的，就交换到 back 上，然后 popback。
给定序列 \(a\)，若 \(a_i\&a_j\neq 0\)，则 \(i,j\) 连边。求这张图的最小环。
发现连边的概率很大，根据抽屉原理，只要 \(n>128\)，必有三元环。
\(n\le 128\) 时跑 Floyd 即可。
SCC 缩点 + DAG 最长路。
给出 \(m\) 对关系 \((a_i,b_i)\)，要求构建一个图，使得所有关系 \((x,y)\) 在图中满足 \(x\) 可达 \(y\)。问至少需要多少条边。
先按给出的关系构建有向图。分成不同连通块考虑。
-
当前连通块是 DAG，按照拓扑序形成一条链即可；
-
不是 DAG，排成一个环即可。
题目：求出一颗生成基环树，边权和最大。
可以在 Kruskal 过程中额外对每个连通块记录这个连通块是树还是基环树。
同样边权排序，但是这次边可以两头都连树，只是不能两头连基环树。
01 分数规划。（其实不用理解得那么玄乎）
首先，越小越好，越大越可行，二分答案 \(mid\)。
接下来判断是否存在一个环的平均值 \(\le mid\)。我们只要给每条边的边权 \(c_i\leftarrow c_i-mid\)，问题就变成判断是否存在负环。
从分数规划角度理解：环就是有些边选了，有些边没选；有些点选了，有些点没选。
令每个点的权值 \(b_u=1\)，答案就是 \(\dfrac{\sum edge}{\sum ver}\)。
二分，\(\dfrac{\sum e}{\sum v}\le mid\iff \sum e-mid\times \sum v\le 0\)，而 \(\sum v\) 就是环上点的个数。所以只要让每条环上的边贡献一个 \(-mid\) 即可。
根据原图 \(G\) 定义一类改造图 \(G_x\)：把 \(G\) 中所有边的边权 \(w\) 改成 \(\max(w-x,0)\)。
若答案路径的第 \(k\) 大的边边权是 \(w_k\)，则 \(ans=G_{w_k}\) 上 \(1\rightarrow n\) 的最短路长度加 \(k\times w_k\)。
若 \(x\neq w_k\)，则 \(G_{w_k}\) 上 \(1\rightarrow n\) 的最短路长度加 \(k\times w_k\) \(>ans\)。
所以枚举 \(w_k\)，求 \(G_{w_k}\) 上最短路，然后把所有最短路长度加 \(k\times w_k\) 取 \(\min\) 就是 \(ans\)。
一定是一条直径 + 离直径最远的点。
从直径上每个点依次出发 BFS 它不经过直径能到的点。
把移动的上下左右改成左上、左下、右上、右下。则最终目的地是 \((A+B,A-B)\)。
（以前移动的方式是 \((\pm d_i,0),(0,\pm d_i)\)。现在每次移动的方式是 \((\pm d_i,\pm d_i)\)）
则 \(x,y\) 两维可以分开考虑。
目标：从 \(d_1\sim d_n\) 中选若干个数和为 \(w=\frac{A+B-\sum d_i}{2}\)。
DP，\(f[i][j]\) 表示前 \(i\) 个数和为 \(j\) 是否可行。
但是这个复杂度是 \(O(n^2D)\) 的，\(i\) 的范围 \(n\)，\(j\) 的范围 \(n\times D.\)（\(D\) 是 \(d_i\) 的上限）
如何优化？
-
bitset 优化。\(O(\dfrac{n^2d}{64})\)。
-
我们找到一个数 \(b\)，\(X=d_1+\dots+d_{b-1}\le w,d_1+\dots+d_b>w\)。
定义 Balanced Set：\(\{1,2,\dots,b-1\}\) 是一个 BS。 所有能通过下列两个操作从 \(\{1,2,\dots,b-1\}\) 变化到达的也是 BS。
-
balanced insert：插入一个 \(\ge b\) 的数。这个操作要求当前的和 \(\le w\)。
-
balanced delete：删除一个 \(<b\) 的数。这个操作要求当前的和 \(>w\)。
观察：所有 BS 的总和 \(\in [w-D,w+D]\)。
（\(D\) 是 \(d_i\) 的上限）
观察：最优解也是一个 BS。
为了方便，重新设状态定义，从 \(b\) 处向两边延申。
\(f_{l,r,j}\) 表示考虑 \([l,r]\) 内的操作，是否可以凑出 \(j\)。
初值 \(f_{b+1,b,X}=true.\)
转移：
-
\(f_{l,r,x}\leftarrow f_{l,r-1,x}\;,\;f_{l+1,r,x}.\)（不选）
-
\(f_{l,r,x+d_r}\leftarrow f_{l,r-1,x}.\;(x\le w)\)
-
\(f_{l,r,x-d_l}\leftarrow f_{l+1,r,x}.\;(x>w)\)
但复杂度还是没变。再重新设计。
\(g_{r,w}\) 表示满足 \(f_{l,r,w}=true\) 的 \(l\) 最大是多少。若不存在则为 \(0\)。
-
\(g_{r,x}\leftarrow g_{r-1,x}.\)
-
\(g_{r,x+d_r}\leftarrow g_{r-1,x}.\;(x\le w)\)
-
\(g_{r,x-d_l}\leftarrow l.\;(x>w,l<g_{r,w})\)
从左边转移但不操作 \(l\) 的情况不用考虑，因为 \(g\) 是取 \(\max\)。
状态数少了，但转移复杂度没变。瓶颈在于第三类转移。
注意到 \(l<g_{r-1,x}\) 时，其会在 \(r-1\) 用第一类转移到。所以只要转移 \(l\ge g_{r-1,x}\) 即可。
对于一个 \(x\)，转移复杂度为 \(O(\sum g_{r,x}-g_{r-1,w})=O(n)\)，所以总复杂度 \(O(nD)\)。
-
易知仅当 \(m\%2=1\) 时无解。
对一颗树：自底向上，每个结点把所有没配好对的儿子两两配。
如果没配对的儿子有奇数个，则 多余的儿子 - 自己 - 父结点 配成一条。
对于图：找 DFS tree，对于回边 \((u,k)\)，\(k\) 是 \(u\) 的祖先。那我们只需要在处理 \(k\) 的时候把 \(u\) 也当作 \(k\) 的儿子即参与配对即可。
找出 DFS tree，判断层数是否直接构成一条路径。
否则，深搜树每一层的结点两两配对，每层最多一个结点没用。
边双缩点，显然一个边双内的边都不确定。
把要向上走视作 +1，向下走视作 -1。对于一个限制 \((x_i,y_i)\)，找到它们所在的边双 \(X_i,Y_i\)，然后让 \(X_i\rightarrow rt\) 的割边权值都 \(+1\)，\(rt\rightarrow Y_i\) 的权值都 \(-1\)，这可以用树上差分。
差分完看看每条边的权值是正是负即可。
数组最后加上一个数等于所有数的异或，每次操作就相当于交换一个数到最后一个位置。
判无解：如果有目标数初始没有，-1；否则必有解。
对于每个 \(a_i\neq b_i\) 的位置，使 \(a_i\) 向 \(b_i\) 连边。
答案 = 边数 + 连通块数 - 1.
一些点的 LCA = dfn 最大最小的结点的 LCA。
所以要改一定是删除 dfn 最值。
用一颗线段树维护。
第一步：建图。
\(O(n^2)\) 肯定是不行的，但我们可以发现：只需要每个点两边最近的能引爆这个点的，向这个点连边即可。
（用单调队列做）这样边数到了 \(O(n)\)。
第二步：求解
SCC 缩点。一个很直接的想法是：每个点引爆的个数，就是它所在 SCC 的后继个数。
但是这是不行的！如果直接找后继，\(O(n^2)\)；而 DP 也不行，因为有后效性了，前面的点不止引爆一个直接后继，还会连着爆一大堆。
那怎么办？
简单的观察：每个炸弹最终引爆的所有炸弹，一定是一个区间。
这样就可以 DP 了，从每个 SCC 缩点做 DP，求出每个 SCC 引爆的左端点和右端点。
标签：回边,图论,le,题目,边权,连通,times,合集,dp From： https://www.cnblogs.com/FLY-lai/p/18016084