prison

54 阅读 0 评论 36 点赞

我是靠谱客的博主辛勤八宝粥，最近开发中收集的这篇文章主要介绍prison，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这个可以状态压缩，用二进制表示，每一位表示第几个选不选
然后就枚举两个子集，合并找最小的组数

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int
N= 1<<17;
int n,m,k,f[N];
bool map[20][20];
int tot;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
--x,--y;
map[x][y]=map[y][x]=1;
}
memset(f,127,sizeof(f));
for(int i=0;i<(1<<n);i++)
{
tot=0;
for(int j=0;j<n;j++)
for(int kk=j;kk<n;kk++)
if(map[j][kk]&&((1<<j)&i)&&((1<<kk)&i))
tot++;
if(tot<=k)
f[i]=1;
for(int j=i;j;j=(j-1)&i)
f[i]=min(f[i],f[j]+f[i^j]);
}
cout<<f[(1<<n)-1];
return 0;
}