Codechef 12.6 MATCH DP+状压DP+期望
题目大意：
给定一个二分图，两侧分别有$n,m$个点，现在给定$P_{i,j}$表示左侧的第$i$个点到右侧的第$j$个点之间有边的概率，求这个二分图的期望最大匹配。
数据范围$n\leq{5},m\leq{100},0\leq{P_{i,j}}\leq{1}$。
算法讨论：
注意到$n\leq{5}$，于是我们只对左侧的点进行考虑。
定义匹配状态表示一个长度为$n$的$01$串，第$i$位为$1$表示左侧的第$i$个点目前是匹配点，否则不是匹配点。显然，不同的匹配状态有$2^{n}$种。
定义匹配状态的集合表示一个长度为$2^{n}$的$01$串，第$i$位表示第$i$种匹配状态目前是不是合法的。
考虑$f_{i,s}$表示只考虑右侧前$i$个点，左侧匹配状态的集合为$s$时概率。
我们枚举所有的$s$，再$O(2^n)$枚举与右侧第$i+1$个点的连边情况，我们计算$f_{i,s}$的贡献：
对于当前的“匹配状态的集合”$s$，我们考虑其中所有的合法匹配状态$state$，枚举与第$i+1$个点相连的左侧的点$x$，若$state[x]=0$，则我们令一个新的状态为$newstate=state,newstate[x]=1$，并将$newstate$扩充入现在的匹配状态的集合。这样我们得到一个新的匹配集合$s'$，令枚举的这种连边的概率为$p$，则我们做转移$f_{i+1,s'}+=f_{i,s}\times{p}$。
这是因为我们对于当前的匹配状态，只能至多再选一个左侧的点加进去与$i+1$匹配。
然而我们发现$s$的状态量是非常大的——能达到$O(2^{2^n})$！
但是实际上我们分析一下，会发现有用的状态很少。
现在假设从空集开始，进行了若干次状态的扩充，每次都是尝试将一系列的点加入匹配：
第一次：$\{2\}$；第二次：$\{1,3\}$，第三次：$\{2,4\}$。
不难发现第三次中的$2$对于匹配集合是没有任何影响的：也就是说每个左侧的点只会在第一次尝试加入匹配集合时产生影响。
于是我们对于一个匹配状态集合，我们只需要考虑尝试加入过匹配集合的左侧点的并集，以及并集的顺序。
由于$n$很小，总状态数不是很多，只有大概$4000$个。
对于每个匹配状态集合，容易知道此时的最大匹配，那么求出概率就能计算答案了。
于是总时间复杂度为$O(4000m2^n)$。
时空复杂度：
时间复杂度$O(4000m2^n)$，空间复杂度$O(4000m)$。
代码：
#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
typedef double f2;
typedef unsigned long long llu;
#define N 10
#define M 110
int n,m;
f2 p[N][M];
llu q[4010];
int fr,ta;
struct Hashset{
static const int mod=13131131;
int head[mod],next[4010],ind,v[4010];
llu f[4010];
inline void reset(){
memset(head,-1,sizeof head);
ind=0;
}
inline int operator[](const llu&x){
int ins=x%mod;
for(int j=head[ins];j!=-1;j=next[j])
if(f[j]==x)
return v[j];
return 0;
}
inline void insert(const llu&x,int _v){
int ins=x%mod;
f[ind]=x;
v[ind]=_v;
next[ind]=head[ins];
head[ins]=ind++;
}
}hash;
llu dhash[4010];
int id;
int max_parti[4010];
int tr[1<<N][4010];
inline void maxi(int&x,int y){
if(x<y)
x=y;
}
int bit_cnt[1<<N];
inline void pre(){
static llu sav[N];
fr=ta=0;
q[ta++]=0;
hash.reset();
hash.insert(0,++id);
dhash[id]=0;
while(fr!=ta){
llu nows=q[fr++];
memset(sav,0,sizeof sav);
for(int i=0;i<(1<<n);++i)
if(i==0||(nows>>i)&1)
for(int j=0;j<n;++j)
sav[j]|=(llu)1<<(i|(1<<j));
for(int i=0;i<(1<<n);++i){
llu tmp=nows;
for(int j=0;j<n;++j)
if((i>>j)&1)
tmp|=sav[j];
if(hash[tmp]==0){
hash.insert(tmp,++id);
dhash[id]=tmp;
q[ta++]=tmp;
}
tr[i][hash[nows]]=hash[tmp];
}
}
for(int i=0;i<(1<<n);++i)
for(int j=0;j<n;++j)
if((i>>j)&1)
++bit_cnt[i];
for(int i=1;i<=id;++i)
for(int j=0;j<(1<<n);++j)
if((dhash[i]>>j)&1)
maxi(max_parti[i],bit_cnt[j]);
}
f2 f[2][4010];
int main(){
cin>>n>>m;
int i,j,k;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
cin>>p[i][j];
pre();
int now=0,last=1;
f[now][hash[0]]=1;
for(i=0;i<m;++i){
swap(now,last);
for(j=1;j<=id;++j)
f[now][j]=0;
for(k=0;k<(1<<n);++k){
f2 _p=1;
for(j=0;j<n;++j)
if((k>>j)&1)
_p*=p[j][i];
else
_p*=(1-p[j][i]);
for(j=1;j<=id;++j)
f[now][tr[k][j]]+=_p*f[last][j];
}
}
f2 ans=0;
for(i=1;i<=id;++i)
ans+=f[now][i]*max_parti[i];
printf("%.6lf",ans+1e-8);
return 0;
}
Sep 19, 2022 01:06:18 AM
Mathematics is one of the tough subjects and also an easy subject for class 10th standard students of TM, EM, AP SSC Maths Model Paper UM and HM studying at government and private schools of the state. Department of School Education and teaching staff of various institutions have designed and suggested the Mathematics question paper with solutions for all chapters topic wide for each lesson of the course, and the AP SSC Maths Model Paper 2023 Pdf designed based on the new revised syllabus and curriculum.