正文
几个解决k染色问题的指数级做法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
几个解决k染色问题的指数级做法
——以及CF908H题解
给你一张n个点的普通无向图，让你给每个点染上k种颜色中的一种，要求对于每条边，两个端点的颜色不能相同，问你是否存在一种可行方案，或是让你输出一种可行方案，或是让你求出满足条件的最小的k。这种问题叫做k染色问题。众所周知，当k>2时，k染色问题是NP的。但是相比$O(k^n)$的暴力搜索来说，人们还是找到了很多复杂度比较优越的指数级做法。本文简单介绍其中几种。
因为对于$O(n^22^n)$来说，$O(n^2)$小得可以忽略不计，所以在本文中我们用$O^*(2^n)$来代替$O(n^{...}2^n)$。
三染色问题
k=3的情况显然比其它的情况更容易入手一些，下面给出几种简单的方法：
1.生成树
先任意求出一个原图的生成树，而对一个生成树染色有$3\cdot 2^{n-1}$种方案，所以暴力即可。
2. 转成2分图
3染色问题可以看成将原图分为3个点独立集的问题。而3个独立集中最小的那个一定不超过$\frac n 3$，所以我们$C_n^{n\over 3}$搜索最小的这部分，然后剩余部分的变成二染色问题，可以在多项式时间内解决。复杂度$\approx O^*({27\over 4})^{n\over 3}\le O^*(1.89^n)$。
3. 随机化+2-SAT
对于每个点，随机扔掉一个颜色不选，然后建图跑2-SAT。因为每个点我们都有$2\over 3$的概率选到正确的颜色，所以期望复杂度是$O^*(1.5^n)$。
当然还有更优越的，其中最厉害的复杂度是$O^*(1.3289^n)$，然而本人并不知道具体做法。。。
k染色问题
这里只讨论k染色的判定性问题，对于k染色的输出方案问题，我们可以不断向原图中加边直到不能k染色为止，此时只需要贪心的求出每个点的染色即可。
1.状压DP
我们带有一点归纳的思想，如果一个集合S能k染色，那么它一定能分成两个部分，一部分能1染色（独立集），一部分能k-1染色。所以我们可以暴力枚举将其分成哪两部分，然后DP即可。时间复杂度是枚举子集的$O^*(3^n)$。
2.容斥原理
考虑一个更难的版本，我们试图统计k染色的方案数，如果方案数>0则有解。（如何输出方案呢？我们可以不断试图向图中加边，最后用朴素的贪心进行染色即可）
k染色的方案数可以看成选出k个独立集，这些独立集覆盖所有点的方案数。由于我们只需要知道方案数是否>0，所以我们甚至可以让这些独立集相交或相同。我们令$c_k(G)$表示G中选出k个独立集覆盖整张图的方案数，考虑容斥，设X是G的一个诱导子图，设a(x)表示x里有多少个独立集。那么$a(x)^k$表示的就是在X中选出k个独立集的方案数（有标号的）。
$c_k(G)=\sum\limits_{X}(-1)^{n-|X|}a(X)^k$
如何求出a数组呢？考虑DP。
我们枚举X中任意一个点v，设$neighbor(v)$表示与v相邻的点的集合，那么$a(X)=1+a(X-v)+a(X-v-neighbor(v))$，分别代表v这个点，不包含v的独立集和包含v且含有至少一个其它点的独立集。
复杂度$O^*(2^n)$。（已知的最优算法）。
3.FWT
我们可以预处理所有独立集，然后用FWT，不断和自己取或卷积，直到$2^n-1$不为0为止。复杂度$O^*(2^n)$。
以上参考：http://www.wisdom.weizmann.ac.il/~dinuri/courses/11-BoundaryPNP/L01.pdf
【CF908H】New Year and Boolean Bridges
题意 ：有一张未知的n个点的有向图，我们设f(a,b)=0/1，表示是否存在一条从a到b的路径。但是你并不知道f(a,b)，取而代之的是，对于任意的a和b，你知道下面3个条件中的一个。
1.f(a,b) and f(b,a) =true
2.f(a,b) or f(b,a) =true
3.f(a,b) xor f(b,a) =true
现在给你n，再给你任意两个点a,b之间满足的条件，让你构造一张符合条件的原图。特别地，令m表示你的图中边的数量，我们希望你的m尽可能小，你只需要输出最小的m即可。
n<=47
题解 ：我们先将and关系形成的连通块缩到一起，如果连通块内存在xor关系则输出无解，否则，我们可以给出一种m可能不是最小的建图方法：
令所有大小>1的连通块内部形成一个环，再用一条链将所有环（以及单个的点）串起来。
这样的话，我们的花费是(n-1+环数)。而我们发现我们可以将某些环合并起来，前提是这些环之间不存在xor关系。如果我们将xor关系看成边，所有环看成点，那么这就变成了k染色问题！因为大小>1的连通块最多只有23个，所以指数级做法是可行的。
具体复杂度：如果用二分+容斥原理的话，复杂度是$O(log^2_n2^n)$的；如果用FWT的话，需要做n次FWT，复杂度是$O(n^22^n)$的，但你会发现每次你只需要对$2^n-1$进行逆FWT，所以复杂度可以优化为$O(n2^n)$。
细节：其实容斥原理或FWT得到的方案数是一个特别大的数，但你只关心这个数是不是0，所以可以采用自然溢出的方式解决。
容斥原理代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int g[(1<<23)+4],Log[(1<<23)+4],cnt[(1<<23)+4];
int n,m;
int f[50],siz[50],bel[50],nr[50];
char str[50][50];
int find(int x)
{
return (f[x]==x)?x:(f[x]=find(f[x]));
}
inline int pm(int x,int y)
{
int z=1;
while(y)
{
if(y&1) z=z*x;
x=x*x,y>>=1;
}
return z;
}
bool check(int x)
{
int ret=0,i;
for(i=1;i<(1<<m);i++) ret+=(((m^cnt[i])&1)?-1:1)*pm(g[i],x);
return ret!=0;
}
int main()
{
scanf("%d",&n);
int i,j,a,b,l,r,mid;
for(i=0;i<n;i++)
{
scanf("%s",str[i]),f[i]=i,siz[i]=1;
for(j=0;j<i;j++) if(str[i][j]=='A'&&find(i)!=find(j)) siz[f[j]]+=siz[f[i]],f[f[i]]=f[j];
}
memset(bel,-1,sizeof(bel));
for(i=0;i<n;i++) if(find(i)==i&&siz[i]>1) bel[i]=m++;
if(!m)
{
printf("%d",n-1);
return 0;
}
for(i=0;i<n;i++) for(j=0;j<i;j++) if(str[i][j]=='X')
{
if(find(i)==find(j))
{
puts("-1");
return 0;
}
a=bel[f[i]],b=bel[f[j]];
if(a!=-1&&b!=-1) nr[a]|=1<<b,nr[b]|=1<<a;
}
for(i=0;i<m;i++) Log[1<<i]=i;
for(i=1;i<(1<<m);i++) a=Log[i&-i],g[i]=1+g[i^(1<<a)]+g[i^(1<<a)^(i&nr[a])],cnt[i]=cnt[i^(1<<a)]+1;
l=1,r=m;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d",n-1+r);
return 0;
}
FWT代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int g[(1<<23)+4],Log[(1<<23)+4],sg[(1<<23)+4];
int n,m,len;
int f[50],siz[50],bel[50],nr[50];
char str[50][50];
int find(int x)
{
return (f[x]==x)?x:(f[x]=find(f[x]));
}
inline int pm(int x,int y)
{
int z=1;
while(y)
{
if(y&1) z=z*x;
x=x*x,y>>=1;
}
return z;
}
inline void fwt(int *a)
{
int h,i,j;
for(h=2;h<=len;h<<=1) for(i=0;i<len;i+=h) for(j=i;j<i+h/2;j++) a[j+h/2]+=a[j];
}
inline int ufwt(int i,int h)
{
if(h==1) return sg[i];
return ufwt(i,h>>1)-ufwt(i-h/2,h>>1);
}
int main()
{
scanf("%d",&n);
int i,j,a,b;
for(i=0;i<n;i++)
{
scanf("%s",str[i]),f[i]=i,siz[i]=1;
for(j=0;j<i;j++) if(str[i][j]=='A'&&find(i)!=find(j)) siz[f[j]]+=siz[f[i]],f[f[i]]=f[j];
}
memset(bel,-1,sizeof(bel));
for(i=0;i<n;i++) if(find(i)==i&&siz[i]>1) bel[i]=m++;
if(!m)
{
printf("%d",n-1);
return 0;
}
for(i=0;i<n;i++) for(j=0;j<i;j++) if(str[i][j]=='X')
{
if(find(i)==find(j))
{
puts("-1");
return 0;
}
a=bel[f[i]],b=bel[f[j]];
if(a!=-1&&b!=-1) nr[a]|=1<<b,nr[b]|=1<<a;
}
for(i=0;i<m;i++) Log[1<<i]=i;
g[0]=1;
len=1<<m;
for(i=1;i<len;i++) a=Log[i&-i],g[i]=g[i^(1<<a)]&(!(i&nr[a]));
fwt(g);
memcpy(sg,g,sizeof(sg));
for(i=1;i<=m;i++)
{
if(ufwt(len-1,len)!=0)
{
printf("%d",n-1+i);
return 0;
}
for(j=0;j<len;j++) sg[j]*=g[j];
}
}
