//import java.io.*;
//import java.util.*;
//import java.util.Arrays;
//import java.util.Collections;
import org.chocosolver.solver.*;
import org.chocosolver.solver.variables.*;
import org.chocosolver.solver.constraints.*;
import org.chocosolver.solver.search.strategy.*;

public class Choco extends MWC {

    Solver solver;      // a solver object, to attach variables and constraints
    IntVar[] vertex;    // vertex[i] = 1 <-> ith vertex selected
    IntVar totalWeight; // sum of weights of selected vertices
    int minWeight;      // minimum vertex weight
    int sumWeight;      // sum of weights
    int [][] adjacent;  // permuted adjacency matrix A
	
    public Choco (int n,int[][]A,int[] degree,int[] weight,int style) {
	super(n,A,degree,weight,style);
	minWeight = Integer.MAX_VALUE;
	sumWeight = 0;
	solver    = new Solver();
	vertex    = VF.enumeratedArray("vertex",n,0,1,solver);
	adjacent  = new int[n][n];

	// permute the graph
	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;
	    minWeight = Math.min(minWeight,weight[i]);
	    sumWeight = sumWeight + weight[i];
	}

	totalWeight = VF.enumerated("totalWeight",minWeight,sumWeight,solver); // dumb

	// non-adjacent vertice cannot be in clique together
	for (int i=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++)
		if (adjacent[i][j] == 0) solver.post(ICF.arithm(vertex[i],"+",vertex[j],"<",2));

	// weight of clique is scalar vertices with weights
	solver.post(ICF.scalar(vertex,weight,totalWeight));
    }

    void search(){
	// heuristic
	if (style == -99)
	    solver.set(ISF.impact(vertex,0));// impact based search, Philippe Refalo, CP2004
	else
	    solver.set(ISF.lexico_UB(vertex));// assign 1st uninstantiated variable to its upper bound
	// optimize
	solver.findOptimalSolution(ResolutionPolicy.MAXIMIZE,totalWeight);
	maxWeight = totalWeight.getValue();
	nodes = solver.getMeasures().getNodeCount();
	// get solution from permuted graph
	for (int i=0;i<n;i++) 
	    if (vertex[i].getValue() == 1) solution[V[i].index] = 1;
    }
}