我的第一轮集训队作业
Codechef 15.5 CBAL 分块

Codechef 12.6 MATCH DP+状压DP+期望

shinbokuow posted @ Nov 20, 2015 03:47:26 PM in Something with tags DP 期望 状压dp , 614 阅读

 

题目大意:
给定一个二分图,两侧分别有$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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter