ABC187F
简要题意
将一个 (n) 个点 (m) 条边的无向图分成 (k) 个部分，使得每个部分都是一个完全图，最小化 (k) 。
样例
3 2 //点数 边数
1 2 //一条边连接的两个节点
1 3 //同上
2 //k的最小值
分成 ({1,2}{3}) 或 ({1,3}{2}) 。
数据范围
(1le nle18) , (0le mlefrac{n imes(n-1)}{2})。
1s，256MB。
题解
发现 (n) 很小，考虑状压。
设 f[i] 表示选的点集为 (i) 时的答案。
设 out[i]表示点集 (i) 中的所有点的出边组成的集合的交集，令 (out[0]=2^n-1)。
设 edge[i] 表示节点 (i) 的出边组成的集合，初始时令 (edge[i]=2^{i-1})。
对于每一个点集 (i) ，如果 (out[i]&i=i) 则说明 (i) 是一个完全图。
枚举 (i) 的子集 (j) ，如果 (j) 是一个完全图那么 (f[i]=min{f[ihat{}j]}+1)。
#include<bits/stdc++.h>
using namespace std;
int n,m,edge[20],End;
int f[1050000],out[1050000],Log[1050000];
inline int read()
{
int x=0,w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return w?-x:x;
}
int main()
{
End=1<<(n=read());m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
edge[x]|=(1<<(y-1));//更新出边集合
edge[y]|=(1<<(x-1));
}
for(int i=1;i<=n;i++){
Log[1<<(i-1)]=i;
edge[i]|=(1<<(i-1));//出边集合中加入自己
}
memset(f,0x3f,sizeof f);
f[0]=0;out[0]=End-1;
for(int i=1;i<End;i++){
out[i]=(out[i^(i&-i)]&edge[Log[i&-i]]);//更新出边集合
if((out[i]&i)==i){f[i]=1;continue;}//如果 i 本身是一个完全图的话就不用枚举子集了
for(int j=i;j;j=(j-1)&i)//枚举 i 的子集
if((out[j]&j)==j)//判断 j 是否是完全图
f[i]=min(f[i],f[i^j]+1);
}
cout<<f[End-1]<<'
';
return 0;
}