Skip to content

Instantly share code, notes, and snippets.

@chaoxu
Created April 6, 2010 19:41
Show Gist options
  • Save chaoxu/357995 to your computer and use it in GitHub Desktop.
Save chaoxu/357995 to your computer and use it in GitHub Desktop.
MSC
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;
}
}
@chaoxu
Copy link
Author

chaoxu commented Apr 7, 2010

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment