[THUWC2017]随机二分图-白红宇

[THUWC2017]随机二分图

阅读量：4632 次

发布时间：2019-06-09

本文共 1155 字，大约阅读时间需要 3 分钟。

题目大意

给一张二分图，有左部点和右部点。

有三种边，第一种是直接从左部点连向右部点，出现概率为50%。

第二种边一组里有两条边，这两条边同时出现或者不出现，概率都是50%。

第三种边一组里有两条边，这两条边只能出现一条，概率都是50%。

求这张图完美匹配数的期望

题解

一条边能够带来贡献的条件不是它出现了，而是它出现在了匹配中。所以我们应当直接计算每条边出现在最大匹配中的概率。

第一种边不用研究。

第二种边每一条条边出现在最大匹配中的概率都是50%。

两条边出现在最大匹配中的概率也是50%。

如果我们直接连两条50%的边的话，两条边同时出现的概率就是25%。

所以我们补一条两组的边，概率为25%。

第三种边同理，两条边出现在最大匹配中的概率是0%。

所以我们补一组-25%的边就好了。

dp的话，拿map记搜一下就好了。

代码

#include
     
      #include
      
       #include
       #define N 16using namespace std;typedef long long ll;const int mod=1e9+7;map
        
         mp;map
         
          ::iterator it; int lo[1<
          
           >=1; } return ans;}inline void MOD(ll &x){ while(x>=mod)x-=mod;}struct edge{ int n,to,l;}e[N*N*2];inline void add(int u,int v){ int loo=lo[u&(-u)]; e[++tot].n=head[loo];e[tot].to=u;head[loo]=tot;e[tot].l=v;}int DP(int s){ if(!s)return 1; it=mp.find(s); if(it!=mp.end())return it->second; int loo=lo[s&(-s)];ll ans=0; for(int i=head[loo];i;i=e[i].n){ int v=e[i].to;if((v&s)!=v)continue; ans+=1ll*DP(s^v)*e[i].l%mod;MOD(ans); } return mp[s]=ans;}int main(){ n=rd();m=rd();int u1,v1,u2,v2,ma=(1<