MSC

msc.java

import java.util.*;

public class msc{
        public static int ub;
        public static ArrayList<Integer> result;
        public static void main(String[] args){
                Scanner in=new Scanner(System.in);
                int e = in.nextInt();
                int n = in.nextInt();
                in.nextLine();
                ArrayList<BitArray> s = new ArrayList<BitArray>();
                for(int i=0;i<n;i++){
                        Scanner line = new Scanner(in.nextLine());
                        BitArray p = new BitArray(i,e);
                        while(line.hasNextInt()){
                                int t = line.nextInt()-1;
                                p.a[t] = true;
                                p.e.add(t);
                                p.size++;
                        }
                        s.add(p);
                }
                ub = n+1;
                Universe u = new Universe(e);
                for(int i=0;i<e;i++){
                        u.e.add(i);
                }
                for(int i=0;i<s.size();i++){
                    for(int j=0;j<s.get(i).size();j++){
                        u.a[s.get(i).e.get(j)]++;
                    }
                }
                u.size = e;
                bb(u, s, new ArrayList<Integer>());
                System.out.println("Minimum Set Cover size: "+ub);
                System.out.println("List of s to chose: "+result);
        }
        public static void bb(Universe u, ArrayList<BitArray> s, ArrayList<Integer> chosen){
                //Prune if we have chosen more than the current best
                if(chosen.size()>=ub){
                        return;
                }
                //If the u is empty, we have chosen a set cover
                if(u.size()==0){
                        ub = chosen.size();
                        result = new ArrayList<Integer>(chosen);
                        return;
                }
                int bv = branch_value(u,s);
                //Remove subset cost O(n^3)
                //It is smarter to test if there is another essential set first
                if(bv==-1){
                         Collections.sort(s);
                         //Prune by upper bound
                         if(chosen.size()==ub-2){
                                if(s.get(0).size()==u.size()){
                                        result = new ArrayList<Integer>(chosen);
                                        result.add(s.get(0).id);
                                        ub--;
                                }
                                return;
                         }
                        //Prune if the sum of the remaining k largest sets can't cover the the u
                        int sum = 0;
                        for(int i=0;i<ub-chosen.size()-1&&i<s.size();i++){
                                sum+= s.get(i).size();
                                if(sum>=u.size()){
                                        break;
                                }
                        }
                        if(sum<u.size()){
                                return;
                        }
                        remove_subs(u, s);
                        bv = branch_value(u,s);
                }
                if(bv!=-1){
                        //Essential Branch 1, prune Branch 0
                        chosen.add(s.get(bv).id);
                        remove_set(u,s,bv);
                        bb(u,s,chosen);
                        chosen.remove(chosen.size()-1);
                }else{
                        //Branch 1, use largest set
                        Universe nu = new Universe(u);
                        ArrayList<BitArray> ns = deep_clone(s);
                        chosen.add(s.get(0).id);
                        remove_set(nu,ns,0);
                        bb(nu,ns,chosen);
                        chosen.remove(chosen.size()-1);
                        //Branch 0, not using the largest set
                        u.removeSet(s.get(0));
                        s.remove(0);
                        bb(u,s,chosen);
                }
        }
        public static ArrayList<BitArray> deep_clone(ArrayList<BitArray> s){
                ArrayList<BitArray> n = new ArrayList<BitArray>();
                for(int i=0;i<s.size();i++){
                        BitArray p = new BitArray(s.get(i));
                        n.add(p);
                }
                return n;
        }
        public static void remove_set(Universe u, ArrayList<BitArray> s, int n){
                BitArray r = s.get(n);
                s.remove(n);
                u.removeAll(r);
                for(int i=0;i<s.size();i++){
                        s.get(i).removeAll(r);
                }
        }
        public static int branch_value(Universe u,ArrayList<BitArray> s){
                //Check if there is any element only covered by one set
                for(int i=0;i<u.size();i++){
                    if(u.a[u.e.get(i)]==1){
                        for(int j=0;j<s.size();j++){
                            if(s.get(j).contains(u.e.get(i))){
                                return j;
                            }
                        }
                    }
                }
                return -1;
        }
        public static void remove_subs(Universe u, ArrayList<BitArray> s){
                for(int i=0;i<s.size();i++){
                        for(int j=i+1;j<s.size();j++){
                                while(j<s.size()&&s.get(i).containsAll(s.get(j))){
                                        u.removeSet(s.get(j));
                                        s.remove(j);
                                }
                        }
                }
        }
}

class Universe{
        public int size;
        public int[] a;
        public ArrayList<Integer> e;
        public int size(){
                return size;
        }
        public Universe(int k){
                a = new int[k];
                size = 0;
                e = new ArrayList<Integer>();
        }
        public Universe(Universe u){
            size = u.size;
            a = Arrays.copyOf(u.a, u.a.length);
            e = new ArrayList<Integer>(u.e);
        }
        public void removeSet(BitArray b){
                for(int i=0;i<b.size();i++){
                        a[b.e.get(i)]--;
                }
        }
        public void removeAll(BitArray b){
                for(int i=0;i<b.size();i++){
                        a[b.e.get(i)] = 0;
                        e.remove(e.indexOf(b.e.get(i)));
                        size--;
                }
        }
}

class BitArray implements Comparable<BitArray> {
        public int size;
        public int id;
        public boolean[] a;
        public ArrayList<Integer> e;
        public int size(){
                return size;
        }
        public BitArray(BitArray b){
                size = b.size;
                a = Arrays.copyOf(b.a, b.a.length);
                e = new ArrayList<Integer>(b.e);
                id = b.id;
        }
        public BitArray(int i, int k){
                a = new boolean[k];
                size = 0;
                id = i;
                e = new ArrayList<Integer>();
        }
        public void removeAll(BitArray b){
                for(int i=0;i<b.size();i++){
                        if(a[b.e.get(i)]){
                                a[b.e.get(i)] = false;
                                e.remove(e.indexOf(b.e.get(i)));
                                size--;
                        }
                }
        }
        public boolean contains(int b){
                return a[b];
        }
        public boolean containsAll(BitArray b){
                for(int i=0;i<b.size();i++){
                        if(!a[b.e.get(i)]){
                                return false;
                        }
                }
                return true;
        }
        public int compareTo(BitArray b){
                if(size>b.size()){
                        return -1;
                }
                if(size==b.size()){
                        return 0;
                }
                return 1;
        }
}

Works bad for the largest k data, strange. All I did is add
if(size==b.size()){
return 0;
}
in compareTo. Which should remove a lot of useless moving around of data during sorting. But of course, it's possible it rarely happens in that data, therefore it doesn't help in anyway except add one more comparison.