407
uva 11825 - Hackers' Crackdown dp
题意
有n个节点，每个节点有m_i个邻居，每个人和邻居为一个整体，问最多可以分成几组使得每组并集合为全集
转移方程
复杂度 3^n
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int node[20];
int ans[1<<17],cover[1<<17];//cover 预处理所有状态下集合并情况
int n;
int main()
{
int C=0;
while(~scanf("%d",&n)&&n)
{
int m,i,j,t;
for(i=0;i<n;i++)
{
node[i]=1<<i;
scanf("%d",&m);
for(j=0;j<m;j++)
{
scanf("%d",&t);
node[i]|=1<<t;
}
}
int Max=(1<<n)-1,S,S0;
for(S=1;S<=Max;S++) //预处理
{
cover[S]=0;
for(i=0;i<n;i++)
if(S&(1<<i))cover[S]|=node[i];
}
for(S=1;S<=Max;S++) //dp
{
ans[S]=0;
for(S0=S;S0;S0=(S0-1)&S)
{
if(cover[S0]==Max)ans[S]=max(ans[S],ans[S^S0]+1);
}
}
printf("Case %d: %d\n",++C,ans[S-1]);
}
}
最后更新：2017-04-03 12:54:53