题面链接

sol

唯一的重点是拆边。。。

0的不管，只看1、2。

先无论如何把两条边的边权赋为\(0.5\)然后我们发现如果两个都选了。

对于第一种边，我们发现如果\(\frac{1}{2} * \frac{1}{2}=\frac{1}{4}\)，但我们实际上需要的是\(\frac{1}{2}\)所以我们连一条两条边都在内的边，权值为\(\frac{1}{4}\)

同理，第二种就是\(-\frac{1}{4}\)

然后就是状压\(dp\)

#include<map>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gt getchar()

#define ll long long

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

inline int in()

{

	int k=0;char ch=gt;

	while(ch<'-')ch=gt;

	while(ch>'-')k=k*10+ch-'0',ch=gt;

	return k;

}

const int YL=1e9+7,inv2=5e8+4,inv4=2.5e8+2;

inline int MO(const int &a){return a>=YL?a-YL:a;}

std::map<int,int>f[1<<16];

#define mk(x,y) ((1<<(x-1))|(1<<(y+n-1)))

int S[1<<16],v[1<<16],cnt,n,m;

int dp(int S_now)

{

	if(!S_now)return 1;

	int T_0=S_now>>n,S_0=S_now&((1<<n)-1);

	if(f[T_0].count(S_0))return f[T_0][S_0];

	int &res=f[T_0][S_0];

	for(int i=1;i<=cnt;++i)

	{

		int T=S[i];

		if((S_now|T)==S_now&&S_now<(T<<1))

			res=MO(res+1ll*dp(S_now^T)*v[i]%YL);

	}

	return res;

}

int main()

{

	n=in(),m=in();

	for(int i=1;i<=m;++i)

	{

		int op=in(),x=in(),y=in();

		int S1=mk(x,y);S[++cnt]=S1,v[cnt]=inv2;

		if(op)

		{

			x=in(),y=in();

			int S2=S[++cnt]=mk(x,y);v[cnt]=inv2;

			if(S[cnt]&S1)continue;

			S[++cnt]=S1|S2;

			v[cnt]=(op==1?inv4:YL-inv4);

		}

	}

	printf("%lld\n",(1ll<<n)*dp((1<<2*n)-1)%YL);

	return 0;

}

巴特西

THUWC2017随机二分图

题面链接

sol

最新文章

热门文章