BZOJ 2891 匹配难题

xiaoxiao2021-02-28  16

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2891

题解

Hall定理:

设一个二分图的两边分别为 U,V U , V ,对于点集 SU S ∈ U ,记录 adj(S) a d j ( S ) 为与 S S 直接有边相连的点(邻集),显然adj(S)Vadj(S)∈V

一个二分图 U,V U , V 有完备匹配的充要条件是:对于任意一个 SU S ∈ U |adj(S)||S| | a d j ( S ) | ≥ | S |

令题目描述中点的数量为 a a 的那边为UU b b VV

定义Hall集合为满足上述条件的点集,所有的Hall集合的集合为HS集。显然,所有Hall集合都 U ∈ U

将所有HS集合对应到一个unsigned long long上面,第 k k 位为11代表HS集合中有二进制状态为 k k 的Hall集合。

由于Hall定理,HS集合的个数不会超过40004000,因此可以用Hash/map映射到一个int上面。

fi,j f i , j 代表 V V 集合中已经选择了[1,i][1,i]这些点, U U 中HS集合在Hash/map中对应的int为jj,造成这种情况的概率为 fi,j f i , j

如果我们能够求出 fi,j f i , j ,那么最终的答案就是 fb,HS×Max(HS) ∑ f b , H S × M a x ( H S ) ,其中 Max(HS) M a x ( H S ) 代表 HS H S 中最大的集合个数。

那么如何求 fi,j f i , j ?显然, f0,=1 f 0 , ∅ = 1

考虑 j j 状态能够转移得到的状态,令gj,kgj,k为:如果当前的HS为 j j ,新加入的点的邻点为kk k k nn个点的二进制状态),那么两个加起来的HS为 gj,k g j , k j,gj,k j , g j , k 为HS的二进制状态对应Hash/map中的int),那么显然有转移: fi,gj,k=fi1,j+P(i,k) f i , g j , k = f i − 1 , j + P ( i , k ) (其中 P(i,k) P ( i , k ) i i 点的邻点的二进制状态为kk的概率)。

考虑如何求出 gj,k g j , k 。分情况讨论:

如果 k k 只有一个点,不妨设这个点的编号为xx

那么现在的集合中是HS集合的情况有两种:

原来就属于HS集合的集合。

加入了这个点 x x 而变成了HS集合的集合。

显然,这种集合满足|adj(S)|=|S||adj(S)|=|S|。经过理性分析可以得到:要满足上述条件,原HS集合必须包含 S{x} S − { x } 这个集合。

因此, gj,k=j+{S{x}j&(S{x})j} g j , k = j + { S ∣ { x } ∈ j & ( S − { x } ) ∈ j } 。其中, & & 表示条件之间的与(C++中的 && & & )。

如果 k k 有多个点。

按上面的思路进行分析,显然可以得到:gj,k=j {Sxk&{x}S&(S{x})j}gj,k=j {S∣x∈k&{x}∈S&(S−{x})∈j},其中 & & 的意义同上。

那么我们就可以求出 g g 数组了,由于求出的gg数组中的元素都是合法的HS集合,因此可以边求 g g 数组边将HS映射到Hash/map中。

时间复杂度:

gg数组:

第一维 O(HS(n)) O ( H S ( n ) ) 第二维 O(2n) O ( 2 n ) 转移 O(n) O ( n ) f f 数组: 第一维O(m)O(m)第二维 O(HS(n)) O ( H S ( n ) ) 转移 O(2n) O ( 2 n )

总时间复杂度: O((n+m)×HS(n)×2n) O ( ( n + m ) × H S ( n ) × 2 n ) ,其中 HS(n) H S ( n ) 代表HS集合中每个元素大小不超过 n n <script type="math/tex" id="MathJax-Element-67">n</script>的集合种类数。

代码

#include <cstdio> #include <map> #include <cmath> #include <algorithm> typedef unsigned long long ull; const int maxn=6; const int maxm=100; const int maxd=4000; const int maxk=(1<<maxn); const double eps=0.001; int n,m,g[maxd+10][maxk+3],full,cnt,size[maxn+10]; ull t[maxk+3],q[maxd+10]; std::map<ull,int> mp; double p[maxn+2][maxm+5],f[maxm+5][maxd+10]; int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { scanf("%lf",&p[i][j]); } } q[1]=mp[1]=cnt=1; int l=0,r=1; while(l<r) { ull now=q[++l]; for(int i=1; i<=n; ++i) { t[i]=now; for(int j=0; j<1<<n; ++j) { if((1ull<<j)&now) { t[i]|=1ull<<(j|(1<<(i-1))); } } } for(int i=0; i<1<<n; ++i) { ull to=now; for(int j=1; j<=n; ++j) { if((1<<(j-1))&i) { to|=t[j]; } } if(!mp.count(to)) { mp[to]=++cnt; q[++r]=to; } g[mp[now]][i]=mp[to]; } } f[0][1]=1; for(int i=1; i<=m; ++i) { for(int j=1; j<=cnt; ++j) { if(f[i-1][j]) { for(int k=0; k<1<<n; ++k) { double e=1; for(int h=1; h<=n; ++h) { if((1<<(h-1))&k) { e*=p[h][i]; } else { e*=1-p[h][i]; } } f[i][g[j][k]]+=f[i-1][j]*e; } } } } double ans=0; for(int i=0; i<1<<n; ++i) { size[i]=size[i>>1]+(i&1); } for(int i=1; i<=cnt; ++i) { if(f[m][i]) { int sz=0; for(int j=0; j<1<<n; ++j) { if((1ull<<j)&(q[i])) { sz=std::max(sz,size[j]); } } ans+=f[m][i]*sz; } } printf("%.2lf\n",ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-2000054.html

最新回复(0)