[USACO03FALL] Popular Cows G 每一头牛的愿望就是变成一头最受欢迎的牛。 现在有 N 头牛，编号从 1 到 N，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。 这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。 你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。 题目链接：P2341，A ...

边的分类 这里先讨论关于边的几种分类，参考《算法导论》给出的定义。 树边：如果结点 vvv 是因算法对边 (u,v)(u,v)(u,v) 的探索而首先被发现，则 (u,v)(u, v)(u,v) 是一条树边。 前向边：将结点 uuu 连接到其在 DFS 树中一个后代结点 vvv 的边 (u,v)(u,v)(u,v)，树边就是一种特殊的前向边。 后向边：将结点 uuu 链接到其在 DFS 树中一个 ...

模板 给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。 若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。 题目链接：AcWing 848。 本题就是要按照入度由小到大排序。 1234567891011 ...

[HEOI2013] Segment 要求在平面直角坐标系下维护两个操作： 在平面上加入一条线段。记第 iii 条被插入的线段的标号为 iii。 给定一个数 kkk，询问与直线 x=kx = kx=k 相交的线段中，交点纵坐标最大的线段的编号。 本题输入强制在线。 输入的第一行是一个整数 nnn，代表操作的个数。 接下来 nnn 行，每行若干个用空格隔开的整数，第 i+1i + 1i+1 行 ...

归并排序求逆序对 由于我们得到的 q[l∼mid],q[mid+1∼r]q[l\sim mid],q[mid+1\sim r]q[l∼mid],q[mid+1∼r] 都是升序排列的，因此只要出现 q[i]>q[j]q[i]>q[j]q[i]>q[j] 就说明 i∼midi\sim midi∼mid 都与 q[j]q[j]q[j] 构成逆序。 1234567891011121314 ...

简介 Prufer 编码用长度为 n-2 的序列表示一个无根树，构造一个 Prufer 序列的方法是： 找到编号最小的叶节点，将它的父结点加入序列。 删除这个节点，如果这个操作使得父结点成为叶结点，并且父结点的编号更小，那么递归处理（如果更大的话会在之后枚举到）。 也就是说，某个点在 Prufer 序列中出现的次数等于它的出度，如果我们设每条边都是父结点指向子结点。 下面证明如果有第 n-1 ...

简介 SAT(Satisfiability) 问题是求使得形如 xi∨xj∨¬xkx_i\lor x_j\lor \neg x_kxi​∨xj​∨¬xk​ 的多个条件式同时成立的一组取值，当每个条件的变量个数大于 2 时已经被证明无法用多项式的复杂度求解，但是如果只有 2 个可以在线性时间内求出可行解。 模板 给定 nnn 个未赋值的布尔变量 x1∼xnx_1 \sim x_nx1​∼xn​，再 ...

流的定义 流网络 G=(V,E)G=(V,E)G=(V,E) 是一个有向图，每条边有一个非负的容量 c(u,v)≥0c(u,v)\ge 0c(u,v)≥0，其中源点为 sss 汇点为 ttt。 流是 fff 一个实值函数，它需要满足下列性质： 容量限制。对于所有的结点 u,v∈Vu,v\in Vu,v∈V 要求 0≤f(u,v)≤c(u,v)0\le f(u,v)\le c(u,v)0≤ ...

简介 树状数组可以看做简化版的线段树，它进行单点修改和区间查询的常数是比线段树更优的。 对于原数组 a[n]a[n]a[n]，树状数组 c[n]c[n]c[n] 是一个等长的数组，并且对于任意 c[i]c[i]c[i] 表示以 a[i]a[i]a[i] 结尾且长度为 lowbit(i)\text{lowbit}(i)lowbit(i) 的区间和。 下面用 f(x)f(x)f(x) 代表 lowbi ...

简介 Dancing Links 是用来解决精确覆盖问题和重复覆盖问题的一个数据结构，它的优势在于一旦问题被转化成精确覆盖或重复覆盖问题，那么就不需要自己想剪枝策略了，直接用 DLX 的剪枝就能达到一个优秀的效果。 DLX 使用十字双向循环链表存储，当然是用数组模拟的链表。 每列对应一个限制条件，每行对应一个选择方案，精确覆盖问题就是满足每个限制条件的同时每个限制条件只被一个选择方案满足，而重复覆 ...