about 2 years ago

前言

好神啊。。。一直不太会做来着。

题目大意

给出一个完全二分图,左边有个点,右边有个点,一共有条边,每条边有一个出现概率,求出最后二分图期望最大匹配。

分析

考虑给出一个二分图我们计算最大匹配的方式(当然不是匈牙利),我们可以利用定理:

其中表示右部中与相邻的元素集合。
那么我们现在的答案就是所有满足定理的集合(简称为)中的元素个数的最大值。
因此我们考虑状态中存的是所有满足定理的集合,也就是一个,集合一共有种,再把这些状态压位就是,一个unsigned即可。
接下来考虑怎样从一个转移到一个新的上去。
考虑不断的加点,每次加入右部的一个点,枚举与左部相邻的集合来转移,设表示当前加入了右部中的前个点,状态为的概率,那么我们要实现的就是,其中为状态,为新点与左部的相邻情况。
原来的是不会变的,考虑新加入的集合,只可能是由于新点产生贡献然后成为的。想一下可以发现只可能是由于原来的加上一个中的点构成的,证明可以利用定理的定义。


所以是可以跑过去的。
MATCH.cpp

← UOJ193:人类补完计划 SPOJ DIVCNT3 →
 
comments powered by Disqus