bzoj 4788: [CERC2016]Bipartite Blanket【hall定理+状压】

考虑当前合法的一个点集s，如果他合法，那么一定有一个完备匹配的点集包含这个点集，也就是两边都满足hall定理的话这两边拼起来的点集也满足要求

所以分别状压两边点集用hall定理转移判断当前点集是否合法，然后分别对两边点集的权值和排个序2point扫一下计算答案即可

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=2000005;

int n,m,ln,lm,t,a[N],b[N],f[N],g[N],p[N],q[N],tp,tq,v[25],w[25],c[N];

long long ans;

char s[25];

int main()

{

	scanf("%d%d",&n,&m);

	ln=(1<<n)-1,lm=(1<<m)-1;

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

	{

		scanf("%s",s+1);

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

			if(s[j]=='1')

				a[(1<<(i-1))]|=(1<<(j-1)),b[(1<<(j-1))]|=(1<<(i-1));

	}

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

		scanf("%d",&w[i]);

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

		scanf("%d",&v[i]);

	scanf("%d",&t);

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

		c[i]=c[i-(i&(-i))]+1;

	for(int s=0;s<=ln;s++)

	{

		f[s]=1;

		int sm=0;

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

			if(s&(1<<(i-1)))

				a[s]|=a[s^(1<<(i-1))],f[s]&=f[s^(1<<(i-1))],sm+=w[i];

		f[s]&=(c[a[s]]>=c[s]);

		if(f[s])

			p[++tp]=sm;//,cerr<<sm<<endl;

	}

	for(int s=0;s<=lm;s++)

	{

		g[s]=1;

		int sm=0;

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

			if(s&(1<<(i-1)))

				b[s]|=b[s^(1<<(i-1))],g[s]&=g[s^(1<<(i-1))],sm+=v[i];

		g[s]&=(c[b[s]]>=c[s]);

		if(g[s])

			q[++tq]=sm;

	}

	sort(p+1,p+1+tp);

	sort(q+1,q+1+tq);

	// for(int i=1;i<=tp;i++)

		// cerr<<p[i]<<" ";cerr<<endl;

	// for(int i=1;i<=tq;i++)

		// cerr<<q[i]<<" ";cerr<<endl;

	for(int i=1,j=tq+1;i<=tp;i++,ans+=tq-j+1)

		while(j-1>0&&p[i]+q[j-1]>=t)

			j--;

	printf("%lld\n",ans);

	return 0;

}

巴特西

bzoj 4788: [CERC2016]Bipartite Blanket【hall定理+状压】

最新文章

热门文章