Skip to content

Instantly share code, notes, and snippets.

@chaoxu
Created April 5, 2010 17:30
Show Gist options
  • Save chaoxu/356630 to your computer and use it in GitHub Desktop.
Save chaoxu/356630 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N=1000;
int counter=0;
int ub;
class bitarray{
public:
int id;
bitset<N> * b;
bitarray(int i){
id = i;
b = new bitset<N>;
}
bitarray(const bitarray& c){
id = c.id;
b = new bitset<N>;
if(b==NULL){
cout<< "DEATH";
exit(1);
}
(*b)|= (*(c.b));
}
int size(){
return (*b).count();
}
void print(){
for(int i=0;i<((*b).size());i++){
cout << ((*b)[i]);
}
cout << "\n";
}
void removeAll(const bitarray& a){
*b &= ~(*(a.b));
}
void add(int i){
(*b).set(i);
}
int contains(int i){
return (*b)[i];
}
int containsAll(const bitarray& a){
if((*b|*(a.b)) == *b){
return 1;
}
return 0;
}
};
void remove_set(bitarray& universe, vector<bitarray>& sets, int pick){
bitarray r (sets[pick]);
sets.erase(sets.begin()+pick);
universe.removeAll(r);
for(int i=0;i<sets.size();i++){
sets[i].removeAll(r);
}
}
void remove_subsets(vector<bitarray>& sets){
for(int i=0;i<sets.size();i++){
for(int j=i+1;j<sets.size();j++){
while(j<sets.size() && sets[i].containsAll(sets[j])){
sets.erase(sets.begin()+j);
}
}
}
}
vector<bitarray> deep_clone(const vector<bitarray>& sets){
vector<bitarray> v;
for(int i=0;i<sets.size();i++){
bitarray p (sets[i]);
v.push_back(p);
}
return v;
}
int set_sorter(const bitarray& a, const bitarray& c){
if(((*(a.b)).count())<((*(c.b)).count())){
return 0;
}
return 1;
}
int branch_value(bitarray& universe, vector<bitarray>& sets){
for(int i=0;i<(*(universe.b)).size();i++){
if(universe.contains(i)){
int c = 0;
int t = 0;
for(int j =0;j<sets.size();j++){
if(sets[j].contains(i)){
t=j;
c++;
if(c==2){
break;
}
}
}
if(c==0){
return -2;
}
if(c==1){
return t;
}
}
}
return -1;
}
void bb(bitarray& universe, vector<bitarray>& sets, vector<int>& chosen){
counter++;
if(chosen.size()>=ub){
return;
}
if((*(universe.b)).none()){
ub = chosen.size();
return;
}
if(chosen.size()==ub-2){
for(int i=0;i<sets.size();i++){
if(sets[i].size() == universe.size()){
chosen.push_back(sets[i].id);
ub = chosen.size();
chosen.pop_back();
return;
}
}
}
sort(sets.begin(),sets.end(),set_sorter);
remove_subsets(sets);
int sum = 0;
for(int i=0;i<ub-chosen.size()&&i<sets.size();i++){
sum+= sets[i].size();
}
if(sum<universe.size()){
return;
}
int bv = branch_value(universe,sets);
if(bv==-2){
return;
}
bitarray nu (universe);
vector<bitarray> ns = deep_clone(sets);
if(bv!=-1){
chosen.push_back(sets[bv].id);
remove_set(nu,ns,bv);
bb(nu,ns,chosen);
chosen.pop_back();
}else{
chosen.push_back(sets[0].id);
remove_set(nu,ns,0);
bb(nu,ns,chosen);
chosen.pop_back();
sets.erase(sets.begin());
bb(universe,sets,chosen);
}
}
int main (){
int e;
int n;
scanf("%d",&e);
scanf("%d",&n);
vector<bitarray> s;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
bitarray p (i);
for(int j=0;j<x;j++){
int t;
scanf("%d",&t);
(*(p.b)).set(t);
}
s.push_back(p);
}
bitarray universe (0);
for(int i=0;i<n;i++){
(*(universe.b))|=(*(s[i].b));
}
vector<int> chosen;
ub = s.size();
bb(universe,s,chosen);
cout<<ub;
cout<<endl;
cout<<counter;
cout<<endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment