Set Cover Using Branch and Bound

#include <bits/stdc++.h>
using namespace std;
#define mem(x,val) memset((x),(val),sizeof(x));
#define write(x) freopen(x,"w",stdout);
#define read(x) freopen(x,"r",stdin);
#define sqr(x) ((x)*(x))
#define pb push_back
#define clr clear()


#define inf (1<<25)
#define NN 1001 //num of elements in universal set = 1000
vector<int> subsets[100]; //num of subsets = 100

int N = NN-1, M = 100;
bool cmp(const vector<int> & a, const vector<int> & b)
{
    return a.size()>b.size();
}

struct Node{
    int level;
    int takenSets;
    int LB;
    int coveredMarks[NN];
    int elementsCovered;
} typedef BBnode;

bool operator<(const BBnode& a, const BBnode& b){
    return a.LB>b.LB;
}

//node dile minimum kotogula subset nite hobe seta bole dibe
int findLB(BBnode node){
    //check this function later
    if(node.elementsCovered==N) return node.takenSets;
    if(node.level==M-1) return inf;
    return node.takenSets + (int)ceil((N-node.elementsCovered) * 1.0 / subsets[node.level+1].size());
}

BBnode setCover(BBnode root){
    priority_queue<BBnode> live;
    BBnode u, v;
    live.push(root);
    while(!live.empty()){
        u = live.top();
        cout<<live.size()<<"$"<<endl;
        live.pop();
        if(u.elementsCovered==N){
            return u;
        }

        //next level e kichu na thakle
        if(u.level==M-1){
            continue;
        }
        v = u;

        //v k nilam na
        v.level++;
        v.LB = findLB(v);
        live.push(v);

        //v k nicchi
        int idx = v.level;
        for(int i = 0; i<subsets[idx].size(); i++){
            if(v.coveredMarks[subsets[idx][i]]==-1){
                v.coveredMarks[subsets[idx][i]] = idx;
                v.elementsCovered++;
            }
        }
        v.takenSets++;
        v.LB = findLB(v);
        live.push(v);
    }
    return root;
}

int main()
{
    int n, m;

    scanf("%d %d", &n, &m); // m is the number of subsets
    N = n; M = m;

    BBnode node;
    node.level = -1;
    node.takenSets = 0;
    node.LB = inf;
    mem(node.coveredMarks, -1);
    node.elementsCovered = 0;

    for(int i = 0; i<m; i++)
    {
        int x;
        char tmp;
        while(1){
            scanf("%d%c", &x, &tmp);
            subsets[i].push_back(x);
            if(tmp=='\n'){
                break;
            }
        }
    }

    //reverse sort using cmp arrays to make a greedy choice
    sort(subsets, subsets+ m, cmp);

    //test if input taken correctly
//    for(int i = 0; i<m; i++)
//    {
//        for(int j = 0; j<subsets[i].size(); j++)
//        {
//            cout<<subsets[i][j]<<' ';
//        }
//        cout<<endl;
//    }


    BBnode ans = setCover(node);
    printf("\n");
    //sobaike na peye thakle root return dbe jetay takenSets 0
    if(n>0 && ans.takenSets==0){
        cout<<"Impossible\n"<<endl;
        return 0;
    }
//    for(int pp = 1; pp<=n; pp++){
//        cout<<ans.coveredMarks[pp]<< ' ';
//    }
//    cout<<endl;
    sort(ans.coveredMarks+1, ans.coveredMarks + n + 1);
//    for(int pp = 1; pp<=n; pp++){
//        cout<<ans.coveredMarks[pp]<< ' ';
//    }
//    cout<<endl;
    cout<<ans.takenSets<<endl;
    for(int i = 1; i<=n; i++){
            //cout<<ans.coveredMarks[i]<<"$"<<ans.coveredMarks[i+1]<<endl;
        if(i==n || ans.coveredMarks[i+1]!=ans.coveredMarks[i]){
            for(int j = 0; j<subsets[ans.coveredMarks[i]].size(); j++){
                cout<<subsets[ans.coveredMarks[i]][j]<<' ';
            }
            cout<<endl;
        }
    }
    return 0;
}