首页 > 代码库 > HDU 5823 color II（FWT）
HDU 5823 color II（FWT）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5823
【题目大意】
定义一张无向图的价值：给每个节点染色使得每条边连接的两个节点颜色不相同的最少颜色数。
对于给定的一张由n个点组成的无向图，求该图的2^n-1张非空子图的价值。
【题解】
设f[i][S]表示i种颜色覆盖S这个集合的方案数，我们只要得到最小的i，f[i][S]大于0，那么i就是S集合的答案。显然有f[i][S]=∑f[1][u]×f[i−1][v](u|v==S)，这个怎么求呢= =，承蒙Claris教导，get新技能FWT，处理位运算形式的卷积，所以我们现在只要求n次FWT，就可以得到答案。
【代码】
#include<cstdio>const int N=18,M=1<<N;char s[N+2];int T,n,i,j,g[N],f[N+1][M],h[M];unsigned int pow[M],ans;void FWT(int*a,int n){ for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){ a[i+j+d]=a[i+j]+a[i+j+d]; }}void UFWT(int*a,int n){ for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){ a[i+j+d]=a[i+j+d]-a[i+j]; }}void mul(){ FWT(h,1<<n); for(i=2;i<=n;i++){ for(j=0;j<1<<n;j++)f[i][j]=f[i-1][j]; FWT(f[i],1<<n); for(j=0;j<1<<n;j++)f[i][j]*=h[j]; UFWT(f[i],1<<n); for(j=0;j<1<<n;j++)f[i][j]=!!f[i][j]; }}int main(){ scanf("%d",&T); for(pow[0]=i=1;i<M;i++)pow[i]=pow[i-1]*233; while(T--){ scanf("%d",&n); for(i=0;i<n;i++){ scanf("%s",s);g[i]=0; for(j=0;j<n;j++)if(s[j]==‘1‘)g[i]|=1<<j; }for(i=0;i<1<<n;i++)f[1][i]=0; for(i=f[1][0]=1;i<(1<<n);i++){ j=i&-i; if(!f[1][i-j])continue; if(g[__builtin_ctz(j)]&i)continue; f[1][i]=1; }for(j=0;j<1<<n;j++)h[j]=f[1][j]; mul(); ans=0; for(i=1;i<1<<n;i++){ for(j=1;!f[j][i];j++); ans+=j*pow[i]; }printf("%u\n",ans); }return 0;}
HDU 5823 color II（FWT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。