NEERC/exclusive/exclusive_mb.java

   1 import java.io.FileReader;
   2 import java.io.IOException;
   3 import java.io.PrintWriter;
   4 import java.util.ArrayList;
   5 import java.util.Scanner;
   6 import java.util.StringTokenizer;
   7
   8 public class exclusive_mb implements Runnable {
   9     private Scanner in;
  10     private PrintWriter out;
  11
  12     private static final int NUM_NODES = 15;
  13
  14     static class Node {
  15         public int color;
  16         public int edgesMask;
  17     }
  18
  19     private final Node[] nodes = new Node[NUM_NODES];
  20
  21     static class Edge {
  22         public int a, b;
  23     }
  24
  25     private final ArrayList<Edge> edges = new ArrayList<Edge>();
  26
  27     public static void main(String[] args) {
  28         new Thread(new exclusive_mb()).start();
  29     }
  30
  31     public void run() {
  32         try {
  33             in = new Scanner(new FileReader("exclusive.in"));
  34             out = new PrintWriter("exclusive.out");
  35
  36             solve();
  37
  38             in.close();
  39             out.close();
  40         } catch (IOException e) {
  41             e.printStackTrace();
  42         }
  43     }
  44
  45     private int nameToIndex(char ch) {
  46         return ch - 'L';
  47     }
  48
  49     private char indexToName(int index) {
  50         return (char) ('L' + index);
  51     }
  52
  53     private void solve() {
  54         for (int i = 0; i < NUM_NODES; i++) {
  55             nodes[i] = new Node();
  56         }
  57
  58         final int numEdges = in.nextInt();
  59         in.nextLine();
  60         for (int i = 0; i < numEdges; i++) {
  61             StringTokenizer stringTokenizer = new StringTokenizer(in.nextLine());
  62             Edge edge = new Edge();
  63             edge.a = nameToIndex(stringTokenizer.nextToken().charAt(0));
  64             edge.b = nameToIndex(stringTokenizer.nextToken().charAt(0));
  65             edges.add(edge);
  66             if ((nodes[edge.a].edgesMask & (1 << edge.b)) == 0) {
  67                 nodes[edge.a].edgesMask |= (1 << edge.b);
  68                 nodes[edge.b].edgesMask |= (1 << edge.a);
  69             }
  70         }
  71
  72         for (int i = 0; i < 1 << NUM_NODES; i++) {
  73             coloringSize[i] = Integer.MAX_VALUE;
  74         }
  75
  76         final int allMask = (1 << NUM_NODES) - 1;
  77         final int waitChainLength = computeMinColoring(allMask) - 2;
  78         out.println(waitChainLength);
  79
  80         int color = 0;
  81         int mask = allMask;
  82         while (mask != 0) {
  83             final int newMask = coloringBacktrack[mask];
  84             final int stableMask = mask & ~newMask;
  85             for (int i : unpackMask(stableMask)) {
  86                 nodes[i].color = color;
  87             }
  88             mask = newMask;
  89             color++;
  90         }
  91
  92         for (Edge edge : edges) {
  93             if (nodes[edge.a].color < nodes[edge.b].color) {
  94                 out.printf("%c %c\n", indexToName(edge.a), indexToName(edge.b));
  95             } else {
  96                 out.printf("%c %c\n", indexToName(edge.b), indexToName(edge.a));
  97             }
  98         }
  99     }
 100
 101     private final int[] coloringSize = new int[1 << NUM_NODES];
 102     private final int[] coloringBacktrack = new int[1 << NUM_NODES];
 103
 104     private int[] unpackMask(int mask) {
 105         int numNodes = 0;
 106         for (int i = 0; i < NUM_NODES; i++) {
 107             if ((mask & (1 << i)) != 0) {
 108                 numNodes++;
 109             }
 110         }
 111         int[] result = new int[numNodes];
 112         int j = 0;
 113         for (int i = 0; i < NUM_NODES; i++) {
 114             if ((mask & (1 << i)) != 0) {
 115                 result[j++] = i;
 116             }
 117         }
 118         return result;
 119     }
 120
 121     private int computeMinColoring(int mask) {
 122         if (coloringSize[mask] != Integer.MAX_VALUE) {
 123             return coloringSize[mask];
 124         }
 125
 126         if (mask == 0) {
 127             return 0;
 128         }
 129
 130         final int[] list = unpackMask(mask);
 131         tryStableSet(list, 0, mask, 0, 0);
 132
 133         return coloringSize[mask];
 134     }
 135
 136     private void tryStableSet(int[] list, int listIndex, int totalMask, int stableMask, int neighborMask) {
 137         if (listIndex == list.length) {
 138             if (stableMask != 0) {
 139                 final int newMask = totalMask & ~stableMask;
 140                 final int size = computeMinColoring(newMask) + 1;
 141                 if (coloringSize[totalMask] > size) {
 142                     coloringSize[totalMask] = size;
 143                     coloringBacktrack[totalMask] = newMask;
 144                 }
 145             }
 146         } else {
 147             tryStableSet(list, listIndex + 1, totalMask, stableMask, neighborMask);
 148
 149             final int j = list[listIndex];
 150             final int thisMask = 1 << j;
 151             if ((neighborMask & thisMask) == 0) {
 152                 tryStableSet(list, listIndex + 1, totalMask, stableMask | thisMask, neighborMask | nodes[j].edgesMask);
 153             }
 154         }
 155     }
 156 }