NEERC/exclusive/exclusive_ft.java

   1 import java.io.BufferedReader;
   2 import java.io.File;
   3 import java.io.FileReader;
   4 import java.io.FileWriter;
   5 import java.io.IOException;
   6 import java.io.PrintWriter;
   7 import java.util.ArrayList;
   8 import java.util.Arrays;
   9 import java.util.StringTokenizer;
  10 import java.util.HashSet;
  11
  12 public class exclusive_ft implements Runnable {
  13
  14         private static final int MAX_N = 100;
  15         private static final int INF = (int) 1e9;
  16         private BufferedReader in;
  17         private StringTokenizer st;
  18         private PrintWriter out;
  19
  20         public exclusive_ft() throws IOException {
  21                 in = new BufferedReader(new FileReader(new File("exclusive.in")));
  22                 st = new StringTokenizer("");
  23                 out = new PrintWriter(new FileWriter(new File("exclusive.out")));
  24         }
  25
  26         public static void main(String[] args) throws IOException {
  27                 new Thread(new exclusive_ft()).start();
  28         }
  29
  30         public void run() {
  31                 try {
  32                         solve();
  33                 } catch (Exception e) {
  34                         e.printStackTrace();
  35                         System.exit(1);
  36                 } finally {
  37                         out.close();
  38                 }
  39         }
  40
  41         private String nextToken() throws IOException {
  42                 while (!st.hasMoreTokens()) {
  43                         st = new StringTokenizer(in.readLine());
  44                 }
  45                 return st.nextToken();
  46         }
  47
  48         private int nextInt() throws NumberFormatException, IOException {
  49                 return Integer.parseInt(nextToken());
  50         }
  51
  52         private void myAssert(boolean u, String message) {
  53                 if (!u) {
  54                         throw new Error("Assertion failed!!! " + message);
  55                 }
  56         }
  57
  58         private void checkBounds(int x, int min, int max, String name) {
  59                 myAssert((min <= x) && (x <= max), name + " is out of bounds: min = " + min + ", max = " + max + ", " + name + " = " + x);
  60         }
  61
  62
  63         private void solve() throws NumberFormatException, IOException {
  64                 int n = nextInt();
  65                 int[][] process = new int[n][];
  66                 int[] cntNeed = new int['Z' - 'L' + 1];
  67                 checkBounds(n, 1, MAX_N, "n");
  68                 for (int i = 0; i < n; i++) {
  69                         String r1 = nextToken();
  70                         String r2 = nextToken();
  71                         myAssert(r1.length() == 1, "");
  72                         myAssert(r2.length() == 1, "");
  73                         char resource1 = r1.charAt(0);
  74                         char resource2 = r2.charAt(0);
  75                         myAssert(('L' <= resource1) && (resource1 <= 'Z'), "Wrong resource: " + r1 + " (process " + (i + 1) + ")");
  76                         myAssert(('L' <= resource2) && (resource2 <= 'Z'), "Wrong resource: " + r2 + " (process " + (i + 1) + ")");
  77                         myAssert(resource1 != resource2, "Process " + (i + 1) + " needs the same resource two times");
  78                         process[i] = new int[] {resource1 - 'L', resource2 - 'L'};
  79                         cntNeed[resource1 - 'L']++;
  80                         cntNeed[resource2 - 'L']++;
  81                 }
  82                 int[] map = new int['Z' - 'L' + 1];
  83                 Arrays.fill(map, -1);
  84                 int size = 0;
  85
  86                 for (int i = 0; i < 'Z' - 'L' + 1; i++) {
  87                         map[i] = size++;
  88                 }
  89
  90                 boolean[][] edge = new boolean[size][size];
  91                 for (int i = 0; i < n; i++) {
  92                         int r1 = process[i][0];
  93                         int r2 = process[i][1];
  94                         edge[r1][r2] = true;
  95                         edge[r2][r1] = true;
  96                 }
  97
  98                 boolean[] isIndependent = new boolean[1 << size];
  99                 for (int mask = 0; mask < (1 << size); mask++) {
 100                         isIndependent[mask] = true;
 101                         checkIndependent:
 102                         for (int i = 0; i < size; i++) {
 103                                 if ((mask | (1 << i)) != mask) {
 104                                         continue;
 105                                 }
 106                                 for (int j = i + 1; j < size; j++) {
 107                                         if ((mask | (1 << j)) != mask) {
 108                                                 continue;
 109                                         }
 110                                         if (edge[i][j]) {
 111                                                 isIndependent[mask] = false;
 112                                                 break checkIndependent;
 113                                         }
 114                                 }
 115                         }
 116                 }
 117                 int all = (1 << size) - 1;
 118                 int[] minColor = new int[1 << size];
 119                 int[] prev = new int[1 << size];
 120                 Arrays.fill(minColor, INF);
 121                 Arrays.fill(prev, -1);
 122                 minColor[0] = 0;
 123                 for (int colored = 0; colored < (1 << size); colored++) {
 124                         if (minColor[colored] == INF) {
 125                                 continue;
 126                         }
 127                         int notColored = all & (~colored);
 128                         for (int subset = notColored; subset > 0; subset = (subset - 1) & notColored) {
 129                                 if (isIndependent[subset]) {
 130                                         int newColored = colored | subset;
 131                                         if (minColor[newColored] > minColor[colored] + 1) {
 132                                                 minColor[newColored] = minColor[colored] + 1;
 133                                                 prev[newColored] = colored;
 134                                         }
 135                                 }
 136                         }
 137                 }
 138
 139                 int[] coloring = new int[size];
 140                 int curColor = minColor[all];
 141                 int curMask = all;
 142                 while (curMask >= 0) {
 143                         int prevMask = prev[curMask];
 144                         int diff = curMask & (~prevMask);
 145                         for (int i = 0; i < size; i++) {
 146                                 if ((diff | (1 << i)) != diff) {
 147                                         continue;
 148                                 }
 149                                 coloring[i] = curColor;
 150                         }
 151                         curMask = prevMask;
 152                         curColor--;
 153                 }
 154
 155                 out.println(minColor[all] - 2);
 156                 for (int i = 0; i < n; i++) {
 157                         int r1 = process[i][0];
 158                         int r2 = process[i][1];
 159                         if (coloring[map[r1]] < coloring[map[r2]]) {
 160                                 out.println(((char) ('L' + r1)) + " " + ((char) ('L' + r2)));
 161                         } else {
 162                                 out.println(((char) ('L' + r2)) + " " + ((char) ('L' + r1)));
 163                         }
 164                 }
 165
 166         }
 167
 168 }