最小费用最大流(MCMF)简要学习笔记
发布于 2021-10-29
在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法,更推荐类似于 Dinic 的 …
在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法,更推荐类似于 Dinic 的 …
题目链接。 发现题解区说大多都是直接说再连一条边权为 $-1$ 的边,在这里略微证明一下正确性。 解析 首先发现若图中没有环,最 …
题意 题目链接。 给定一张有向无自环图,求一个点集满足: 点集内任意两个不同点距离不小于 $2$(即无边相连)。 对于任意一个不在 …
题意 题目链接 给出一个正方形区域,其中有一些点是障碍。每次询问给出两个球的初始位置,询问至少需要改变几次重力才能使两球相遇。 解 …
题目链接 题意 给定一个二分图,二分图上的每个点都有一个权值。如果一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$ …
题意 题目链接 需要寻找一种可行的候选人列表并输出,注意每个人在候选人列表找出第一个自己的祖先就会送出礼物。 解析 首先,如果一个 …
这题搞了好久才搞过 题意 题目链接 注意,如果他有一种方案能够满足 “Win” 的条件,这时即使有环,结果仍然为 “Win” 。 …
题意 题目链接 easy version 中要求的是将第一条边最大修改为多少能够使其存在在最小生成树中。 解析 题目与最小生成树相 …
为什么这么裸的题是紫题。 题意 题目链接 注意权值最小值指的是这 $k$ 条边中权值最小的那条边的值就好,题意叙述的很清楚了。另外 …