import java.util.*; public class Tours_john { public static final int MAX = 20; // max number of cities in a district public static final int MAXD = 50; // max # of districts public static final double INF = 10000000.0; public static double[][] dists = new double[MAX][MAX]; // used to calculated TSP for a given district public static double[][] combined; // TSP values for all possible fired/not-fired district matchings public static district[] districts = new district[MAXD]; public static double calcEuclidean(point p1, point p2) { double dx = p1.x - p2.x; double dy = p1.y - p2.y; return Math.sqrt(dx*dx + dy*dy); } public static double buildTable(int n) { Queue q = new LinkedList<>(); double[][] table = new double[1<<(n-1)][n-1]; int startv = n-1; for(int i=0; i adj; public int vnum; public double price; public double dist; public Vertex prev; public boolean visited; public Vertex(String nm, int n) { name = nm; adj = new LinkedList(); vnum = n; price = dist = Graph.INFINITY; prev = null; } public String toString() { return name; } public void updatePrice() { price += dist; } public void reset() { dist = Graph.INFINITY; prev = null; visited = false; } } class Edge { public Vertex dest; public double cost; public double reducedCost; public Edge(Vertex d, double c) { dest = d; cost = c; } public void setReduced(double srcPrice) { reducedCost = cost + srcPrice - dest.price; } } class Path { public int length; public Vertex[] path; public Path(int max) { path = new Vertex[max]; length = 0; } public void build(Vertex v) { if (v == null) return; build(v.prev); path[length++] = v; } public String toString() { String s = path[0].name; for(int i=1; i" + e.reducedCost); } } } } class Matching { public Vector first; public Vector second; public Matching() { first = new Vector(); second = new Vector(); } public void update(Path p) { first.add(p.path[1]); second.add(p.path[2]); //System.out.println("add " + p.path[1] + "-" + p.path[2]); for(int i=2; i