问题描述 SAT(satisfiabality) 是适应性的缩写，一般称 k 的适应性问题为 k-SAT。适应性问题指有 \(n\) 个布尔变量 \(\{x_i\}\)，加入一些限制然后求限制内的解的问题。 因为 \(k>2\) 的 k-SAT 问题是 NP 完全问题（没有一定的算法和正解），我们只讨论 2-SAT 问题。 Tarjan 一般来讲，我们会想到把变量 \(x...

AT2390 Games on DAG 题意 \(n\) 个点 \(m\) 条边的 DAG，每条边 \((u,v)\) 有 \(u<v\)。\(1,2\) 号点各一个石头，Alice 和 Bob 轮流每次沿边移动一个石头，不能动者输。求所有连边子集中先手胜的情况。两个石头可以重合。\(n\leq 15\)。 思路 发现对于两个石头的 SG 函数是独立的，输者两个石头 SG 函...

CF487E Tourists 前排膜拜T神 上面的话和这道题一点关系都没有 题意 给一个点带权的无向图，每次询问查询两点间所有简单路径上最小值的最小值，单点修改。 思路 一眼圆方树。 ——@gxy001 这种题只有在树上做才比较好处理这么多次询问。考虑广义圆方树，缩完点双连通分量后建立的方点和圆点。 因为我们找的是最小值，所以必须将代表整个点双的方点的权值设为与其...

CF437D The Child and Zoo 题意 给定一个无向图，求所有点对间所有简单路径上最小点权的最大值的平均值。 思路 首先，我们可以将点权转移到边权上，边权为两端点点权的较小值。正确性显然。 然后，对于任意两个点之间的贡献，只有路径上含最大点权的简单路径有贡献，于是就可以把无向图转变为最大生成树。任意两个点间的贡献显然是在最大生成树上路径的最大边权。 考虑对于一...

我之前一直记的迪杰斯特拉的翻译导致我把 dijkstra 写成了 dijstra 或者 dijskra…… 我以后叫她迪杰克斯歘！ dijkstra 是用来在有向图或者无向图中寻找任意两个点的最小距离的算法。但是无法处理带负环的图和求最长路。 dijkstra 的核心思想是由已找到的最短路的点集每次扩展一个点的最短路。 dis 数组代表由起点到其他点的最短路，初始化其为 \(I...

LCT维护一个森林，即把每个节点用splay维护，可以进行许多操作： 查询、修改链上的信息 随意指定原树的根（即换根） 动态连边、删边 合并两棵树、分离一棵树 动态维护连通性 等 主要性质 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。 每个节点仅包含于一个splay中。 边分为实边和虚边...

P2491 消防/P1099 树网的核 双倍经验，双倍快乐。 题意 在一个树上选择一段总长度不超过\(s\)的链使所有点到该链距离的最大值最小。 输出这个最小的值。 做法 Define:以下\(s\)指链或链长。 证明一下\(s\)一定处于直径上。假设它不在直径上，一定存在直径的其中一个端点到\(s\)的距离大于现在所处支链的最大距离。所以\(s\)不在直径上一定不优。 ...

平面图 平面图就是所有点的连边可以在平面上不相交的图。这一点可以大概理解成拓扑图的性质，即每连一条边就会将某个区域进行分割——很明显，如果两个点分别处在两个不可达的区域，它们要连边显然是要穿过其他边的。 平面图定理 边数大于点数的三倍减六的图一定不是平面图。即设n为点数，m为边数，有 \[m<=n*3-6\] 关于平面图的其他定理和上定理的证明我不会不过我有大佬博客就不乱搬了...

P4180 [BJWC2010]严格次小生成树 题意 求出一个无向联通图的严格次小生成树。严格次小生成树的定义为边权和大于最小生成树的边权和但不存在另一棵生成树的边权和在最小生成树和严格次小生成树之间（不相等）。 思路 先求出一颗最小生成树，发现严格次小生成树一定是其断了一条边并加了一条边且边权和的增加量最小。 那么我们继续在最小生成树上做。对于每一条不是最小生成树上的边，求出其两...

P4494 [HAOI2018]反色游戏 题意 给你一个无向图，图上每个点是黑色或者白色。你可以将一条边的两个端点颜色取反。问你有多少种方法每个边至多取反一次使得图上全变成白色的点。 思路 若任意一个连通块黑色点的个数为奇数那么无解。 先考虑树的情况。发现如果是树，并且黑点个数为偶数，有且仅有一种方式达到目标。然后发现，对于一个无向图，它的任意一个生成树若有解，那么其他非树边无论是...