JZOJ 6316.djq的朋友圈【状压】

...

• 题目：
• 题意：
• 分析：
• 代码：

题目：

传送门

题意：

给出关系表，求一个对比的顺序，使得可能的盟友数最大

分析：

设 A A A表示直接与 1 1 1相连的点集， B B B表示直接与 A A A相连但不与 1 1 1相连的点集

那我们显然可以用状压来表示 A A A中选择的情况，但这样对于 100 % 100\% 100%的数据来说，这样的复杂度就是 O ( 2 42 ) O(2^{42}) O(242)的了

那怎么优化呢，我们看到 B B B集合同样可以计算出答案，所以我们对于大小较小的那个点集进行状压就可以巧妙的 A C AC ACl

代码：

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#define LL long long 
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}
LL t[50][50],n,m,tf[50];
LL c1,c2,id[50];
LL w[50],zt[50],f[(1<<23)];
int main()
{
	freopen("friends.in","r",stdin);
	freopen("friends.out","w",stdout);
	n=read(),m=read();
	memset(t,-1,sizeof(t));memset(id,-1,sizeof(id));
	for(LL i=1;i<=m;i++)
	{
		LL x=read(),y=read();
		t[x][y]=t[y][x]=read();
	}
	LL ans=0;
	for(LL i=2;i<=n;i++)
	{
		if(t[1][i]==-1) continue;
		id[i]=c1++;ans+=(t[1][i]^1);
		for(LL j=2;j<=n;j++)
		{
			if(t[1][j]==-1&&t[i][j]!=-1)
			{
				if(id[j]==-1) id[j]=c2++;
				zt[id[i]]|=(1ll<<id[j]);
				w[id[i]]|=((t[1][i]^t[i][j]^1)<<id[j]);
			}
		}
	}
	memset(f,0xcf,sizeof(f));
	f[0]=0;
	if(c1<=20)
	{
		for(LL i=0;i<(1<<c1);i++)
		{
			if(f[i]<0) continue;
			LL bc=0;
			for(LL j=0;j<c1;j++) if((i>>j)&1) bc|=zt[j];
			for(LL j=0;j<c1;j++)
			{
				if(i>>j&1) continue;
				LL next=(i|(1<<j)),s=f[i]+__builtin_popcountll(w[j]&(~bc));
				f[next]=max(f[next],s);
			}
		}
		ans+=f[(1<<c1)-1];
	}
	else
	{
		for(LL i=0;i<(1<<c2);i++)
		{
			if(f[i]<0) continue;
			for(LL j=0;j<c1;j++)
			{
				if(((i|zt[j])==i)) continue;
				LL next=(i|zt[j]),s=f[i]+__builtin_popcountll(w[j]&(~i));
				f[next]=max(f[next],s);
			}
		}
		ans+=f[(1<<c2)-1];		
	}
	cout<<ans;
	return 0;
}