//
// Ostergard's Cliquer, using his ordering
// Can be compared to Glasgow Doll
//

import java.util.*;

class CliquerO extends MWC {

    long[] c; // weight of max clique using vertices 0 to i inclusive
    int [][] adjacent; // permuted adjacency matrix A

    CliquerO (int n,int[][]A,int[] degree,int[] weight,int style) {
	super(n,A,degree,weight,style);
	cpuTime  = System.currentTimeMillis();
	nodes    = 0;
	c        = new long[n];
	adjacent = new int[n][n];

	orderVertices();
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++){
		int u = V[i].index;
		int v = V[j].index;
		adjacent[i][j] = A[u][v];
	    }
	for (int i=0;i<n;i++) weight[i] = V[i].weight;
    }

    void search(){
	for (int i=n-1;i>=0;i--){
	    ArrayList<Integer> P = new ArrayList<Integer>(n-i);
	    ArrayList<Integer> C = new ArrayList<Integer>(n-i);
	    long pWeight = 0;
	    C.add(i);
	    for (int j=i+1;j<n;j++){
		if (adjacent[i][j] == 1){
		    P.add(j);
		    pWeight = pWeight + weight[j];
		}
	    }
	    expand(C,P,weight[i],pWeight);
	    c[i] = maxWeight;
	}
    }

   
    void expand(ArrayList<Integer> C,ArrayList<Integer> P,long cWeight,long pWeight){
	nodes++;
	if (P.isEmpty() && cWeight > maxWeight){
	    saveSolution(C,cWeight);
	    return;
	}
	while (!P.isEmpty()){
	    if (cWeight + pWeight <= maxWeight) return;
	    int v = P.get(0);
	    if (cWeight + c[v] <= maxWeight) return;
	    ArrayList<Integer> newP = new ArrayList<Integer>();
	    long newPWeight = 0;
	    for (int w : P){
		if (adjacent[v][w] == 1){
		    newP.add(w);
		    newPWeight = newPWeight + weight[w];
		}
	    }
	    C.add(v);
	    expand(C,newP,cWeight+weight[v],newPWeight);
	    C.remove((Integer)v);
	    P.remove((Integer)v);
	    pWeight = pWeight - weight[v];
	}
    }

    void saveSolution(ArrayList<Integer> C,long cWeight){
	Arrays.fill(solution,0);
	for (int i : C) solution[V[i].index] = 1;
	maxWeight = cWeight;
	whenFound = nodes;
	if (trace) System.out.println("saved -> nodes: " + nodes +" weight: "+ maxWeight +" "+ C);
    }
}