RainAir
My OI Blog
RainAir

二分图
文章归档

ARC099 题解

C - Minimization 普及组题,不说了。 代码 D - Snuke Numbers 题意 将 $x$ 的数字和记作 $S(x)$。 称 $n$ 是好的,当且仅当 $\forall m>n, n \leq m$ 。 求第 $K$ 个好的数字。 保证答案不超过 $10^{15}$。 题解 全场最难的题。。。 我们设 $f(x)$ 表示满足 $\f…

   55   2019-10-18   55 去吊打作者

「BZOJ 4788」[CERC2016]Bipartite Blanket

题目大意 二分图点有点权,定义点集的权值为点权和,统计二分图中有多少个点集,满足被至少一个匹配覆盖。 $n,m \leq 20$ 题解 首先你要知道一个叫做霍尔定理的东西:设 $G$ 中有一组匹配,一端恰好为组成 $X$ 的点的充分必要条件是: $X$ 中的任意 $k$ 个点至少与…

   203   2019-08-26   203 去吊打作者

「二分图模板」距离序列

题目描述 已知序列 $S={0,1,\cdots ,n-1}$,序列里有 $n$ 个数,从 $0$ 到 $n-1$。定义两个数 $x,y$ 的距离 $D(x,y) = min{|x-y|,N-|x-y|}$. 定义序列 S 的一个排列 T ,那么这两个序列的距离序列 $Q(S,T) = {D(S_0,T_0),D(S_1,T_1),\cdots,D(…

   380   2018-11-27   380 去吊打作者

二分图最大匹配

二分图定义 二分图是图论中的一种特殊模型,是图论中的一种特殊的模型。我们设$ G(V,E) $是一个无向图,如果顶点$ V $能被分割为两个互不相交的子集,并且图中的每条边$ (i,j) $所关联的两个顶点$ i $和$ j $分别属于这两个不同的顶点集,则称图$ G $为一个二分图。 …

   627   2018-01-07   627 去吊打作者
标签
近期评论