RainAir
My OI Blog
RainAir

二分图
文章归档

「BZOJ 4788」[CERC2016]Bipartite Blanket

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

   145   2019-08-26 去围观

「二分图模板」距离序列

题目描述 已知序列 $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(…

   340   2018-11-27 去围观

二分图最大匹配

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

   559   2018-01-07 去围观
标签
近期评论