NEERC/exclusive/exclusive_rs.java

   1 import java.io.*;
   2
   3 public class exclusive_rs implements Runnable {
   4     private BufferedReader in;
   5     private PrintWriter out;
   6
   7     private void check(boolean expr, String msg) {
   8         if (!expr) {
   9             throw new Error(msg);
  10         }
  11     }
  12
  13     private void checkBounds(int n, int low, int hi, String nStr) {
  14         check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  15     }
  16
  17     private void solve() throws IOException {
  18         int n = Integer.parseInt(in.readLine());
  19         int m = 15;
  20         checkBounds(n, 1, 100, "n");
  21         int[] px = new int[n];
  22         int[] py = new int[n];
  23         boolean[][] go = new boolean[m][m];
  24         for (int i = 0; i < n; i++) {
  25             String line = in.readLine();
  26             check(line.length() == 3, "invalid line: " + line);
  27             px[i] = line.charAt(0) - 'L';
  28             py[i] = line.charAt(2) - 'L';
  29             checkBounds(px[i], 0, 14, "resource number");
  30             checkBounds(py[i], 0, 14, "resource number");
  31             check(px[i] != py[i], "some process has same resources");
  32             go[px[i]][py[i]] = true;
  33             go[py[i]][px[i]] = true;
  34         }
  35
  36         boolean[] isAnticlique = new boolean[1 << m];
  37         LOOP:
  38         for (int mask = 0; mask < (1 << m); mask++) {
  39             isAnticlique[mask] = true;
  40             for (int i = 0; i < m; i++) {
  41                 for (int j = i + 1; j < m; j++) {
  42                     if (((mask & (1 << i)) != 0) && ((mask & (1 << j)) != 0) && go[i][j]) {
  43                         isAnticlique[mask] = false;
  44                         continue LOOP;
  45                     }
  46                 }
  47             }
  48         }
  49
  50         int[] ans = new int[1 << m];
  51         int[] prev = new int[1 << m];
  52         for (int mask = 0; mask < (1 << m); mask++) {
  53             if (isAnticlique[mask]) {
  54                 ans[mask] = 1;
  55                 prev[mask] = mask;
  56                 continue;
  57             }
  58             ans[mask] = m;
  59             for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
  60                 if (!isAnticlique[submask]) {
  61                     continue;
  62                 }
  63                 if (ans[mask ^ submask] + 1 < ans[mask]) {
  64                     ans[mask] = ans[mask ^ submask] + 1;
  65                     prev[mask] = submask;
  66                 }
  67             }
  68         }
  69
  70
  71         int curMask = (1 << m) - 1;
  72         out.println(ans[curMask] - 2);
  73         int count = 0;
  74         int[] p = new int[m];
  75         while (curMask > 0) {
  76             int mask = prev[curMask];
  77             for (int i = 0; i < m; i++) {
  78                 if ((mask & (1 << i)) != 0) {
  79                     p[i] = count++;
  80                 }
  81             }
  82             curMask ^= mask;
  83         }
  84         for (int i = 0; i < n; i++) {
  85             if (p[px[i]] < p[py[i]]) {
  86                 out.println((char) ('L' + px[i]) + " " + (char) ('L' + py[i]));
  87             } else {
  88                 out.println((char) ('L' + py[i]) + " " + (char) ('L' + px[i]));
  89             }
  90         }
  91     }
  92
  93     public static void main(String[] args) {
  94         new Thread(new exclusive_rs()).start();
  95     }
  96
  97     public void run() {
  98         String problem = getClass().getName().split("_")[0];
  99         try {
 100             in = new BufferedReader(new FileReader(new File(problem + ".in")));
 101             out = new PrintWriter(new File(problem + ".out"));
 102             solve();
 103             in.close();
 104             out.close();
 105         } catch (IOException e) {
 106             e.printStackTrace();
 107             System.exit(1);
 108         }
 109     }
 110 }