在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法，更推荐类似于 Dinic 的 spfa+dfs 的写法，详见最下方的“附加代码”部分。 MCMF（基于 spfa 实现） 模板题：Luogu3381。 即给定一张网络，每条边都有一个权值和流量限度，这条边上每有一个流量，总费用就加上这个权值，你需要在…

题目链接。 发现题解区说大多都是直接说再连一条边权为 $-1$ 的边，在这里略微证明一下正确性。​ 解析 首先发现若图中没有环，最大答案为所有联通块的最长链长度之和，最小答案为 $3$。 若存在环，则最大答案为所有环的 $\gcd$​​。为了在可接受的时间内找到所有环，我们对于每一条边的 $u\rightarrow v$​​，从 $u$​​ 向 $…

题意 题目链接。 给定一张有向无自环图，求一个点集满足： 点集内任意两个不同点距离不小于 $2$（即无边相连）。 对于任意一个不在点集内的点，存在一个点集内的点到它的距离不大于 $2$（即两步能达）。 解析 算法实现与 @Mickey_snow、@_Anchor 等题解类似，本篇题解主要重申一种可能更清晰的证明以及错解的 Hack。 简单阐述解法：…

题意 题目链接 给出一个正方形区域，其中有一些点是障碍。每次询问给出两个球的初始位置，询问至少需要改变几次重力才能使两球相遇。 解析 首先我们发现，实际上仅有障碍周围（包括地图边界）上的点是有意义的（因为任何位置的球经过一次操作一定会到这些点，显然一次操作是可以枚举的）。我们定义每一组有意义的 $(x,y)$ 为一个状态，显然最多状态数为 $200…

博客参考：学委 的 博客 及 代码启示 暴力最大流 模板题：Luogu3376 在学习 Dinic 之前，必须先要知道暴力最大流的写法。 首先理解何为网络最大流。一张网络就是一张带权有向图，源点可以输出无限的流量，但是每一条边都有一个容量，需要满足这条边上的流量不能超出其容量（可以理解为输水系统），最后所有流量都会被汇点接收。我们需要求出这个网络运…

题目链接 题意 给定一个二分图，二分图上的每个点都有一个权值。如果一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$，则这两点之间有一条边。求二分图最大匹配。 解析 首先我们发现，如果暴力建边的话，我们可能会建 $n^2$ 条边，在 $100$ 组数据的情况下，非常容易 TLE。 我们考虑优化。对于一个左部点的权值和一个右部点的权值的…

题意 题目链接 需要寻找一种可行的候选人列表并输出，注意每个人在候选人列表找出第一个自己的祖先就会送出礼物。 解析 首先，如果一个人是某一个人的送礼物目标，则这个人就一定会出现在答案序列里。 而如果一个人的祖先已经出现在名单里了的话，则这个祖先的所有儿子即使后续再在列表中出现，也是无意义的。因此我们考虑拓扑排序，建一张反图，并得出该图的拓扑序，再除…

这题搞了好久才搞过 题意 题目链接 注意，如果他有一种方案能够满足 "Win" 的条件，这时即使有环，结果仍然为 "Win" 。 解析 题目要求判断从起点走若干奇数步数能否到达一个无法走的点，即没有出度的点。因此我们只需要先标记下没有出度的点，再从起点开始 dfs ，判断有没有一次走到没有出度的点时步数为奇数步即可。 然而具体 dfs 的实现没有这…

题意 题目链接 easy version 中要求的是将第一条边最大修改为多少能够使其存在在最小生成树中。 解析 题目与最小生成树相关，又要值尽可能大，很容易想到 kruskal 算法，因为该算法是先将权值小的边加入到最小生成树中的，因此，我们希望第一条边能够尽可能晚的加入到最小生成树中，这样才能使其权值最大。 考虑到要使其尽可能晚加入而且不能不加入…

为什么这么裸的题是紫题。 题意 题目链接 注意权值最小值指的是这 $k$ 条边中权值最小的那条边的值就好，题意叙述的很清楚了。另外注意点号是从 $0$ 开始的。 解析 一看数据范围, $1 \le k \le 10^{10}$ ,很显然正常跑跑不了，既然要快速跑，而本题中又没有对边的权值进行改变，再给了每个点有且仅有一条出边，很容易就能想到倍增。 …