bzoj 1135: [POI2009]Lyz Hall定理

2018-04-26

似乎是Hall定理为数不多的题目之一。

先说一下hall定理内容:

设二分图中G=<V1,V2,E>中 |V1|=m<=|V2|=n,G中存在从V1到V2的完全匹配当且仅当V1中任意k(k=1,2,…,m)个顶点至少关联V2中k个顶点。

证明:(口胡

充分性:反证法。设G中不存在完全匹配,取G的一个最大匹配M,则V1中至少有一个点不在M上,且该点必至少与一条不在M中的边相连,该边的另一个顶点若也为M-非饱和点,则与M为最大匹                  配矛盾,若另一个顶点为M-饱和点,则考察在M中与该顶点相邻的点,利用饱和点去考察在M中相邻的饱和点(交错地考察,即交错地通过M中的边和非M中的边),直至考察完毕,由相                异性条件知,最后必考察至非饱和点,此时出现一条增广路,又与假设矛盾(M不是最大匹配),故充分性成立。

必要性:显然成立,若V1中某k各节点在V2中关联的顶点数小于k,那么这k个点一定无法全部匹配。

hall定理推论内容:

设二分图中G=<V1,V2,E>中|V1|=m<=|V2|=n,V1中每个顶点至少关联正整数t条边,V2中每个顶点至多关联t条边,则G存在从V1到V2的完全匹配。

证明:可以转化为hall定理

然后来说这道题:

可以发现当且仅当对于每i个人,都至少有i个鞋子穿时,有解,否则无解。

如果我们选出的i个人是不连续的,那么我们一定可以把另一些人填进去,所以不用考虑。

我们只需要考虑,对于连续的一些人,是否有完全匹配方案。

于是我们可以得到,对于任意的l,r,都满足\(\sum_{i=l}^{r}v_i \leq \left ( r-l+1+d \right )*k\)时,有可行方案。

然而这个式子需要我们枚举每一个l,r,于是我们令上式中的vi=vi-k

然后我们就得到\(\sum_{i=l}^{r}v_i \leq d * k\)

我们发现k*d是个定值,于是我们只需要求出另等式左边的值最大的一组l,r,然后与k*d比较大小即可。

我们可以用线段树维护此过程,注意我们维护的是vi-k,所以每个节点的初始值应为-k。

奉上代码:

 

 

 

Leave a Reply:

电子邮件地址不会被公开。 必填项已用*标注