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