NEERC/inspection/inspection_rs.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class inspection_rs implements Runnable {
   5     private BufferedReader in;
   6     private PrintWriter out;
   7
   8     private void check(boolean expr, String msg) {
   9         if (!expr) {
  10             throw new Error(msg);
  11         }
  12     }
  13
  14     private void checkBounds(int n, int low, int hi, String nStr) {
  15         check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  16     }
  17
  18     private boolean[][] go, w;
  19     private int[][] flow, cap, ans;
  20     private boolean[] mark;
  21     private int[] path;
  22     private int n, count;
  23
  24     private static final int MAXW = 10000;
  25
  26     private void solve() throws IOException {
  27         n = Integer.parseInt(in.readLine());
  28         checkBounds(n, 1, 100, "n");
  29         go = new boolean[n][n];
  30         w = new boolean[n][n];
  31         for (int i = 0; i < n; i++) {
  32             StringTokenizer st = new StringTokenizer(in.readLine());
  33             int w = Integer.parseInt(st.nextToken());
  34             for (int j = 0; j < w; j++) {
  35                 int u = Integer.parseInt(st.nextToken()) - 1;
  36                 check(u != i, "Edge from vertix to itself");
  37                 check(!go[i][u], "Duplicate edges");
  38                 go[i][u] = true;
  39             }
  40         }
  41
  42         for (int i = 0; i < n; i++) {
  43             for (int j = 0; j < n; j++) {
  44                 for (int k = 0; k < n; k++) {
  45                     if (w[j][i] && w[i][k]) {
  46                         w[j][k] = true;
  47                     }
  48                 }
  49             }
  50         }
  51         for (int i = 0; i < n; i++) {
  52             check(!w[i][i], "graph is not acyclic");
  53         }
  54
  55         int s = n;
  56         int t = n + 1;
  57         flow = new int[n + 2][n + 2];
  58         cap = new int[n + 2][n + 2];
  59         int[][] baseFlow = new int[n + 2][n + 2];
  60         for (int i = 0; i < n; i++) {
  61             for (int j = 0; j < n; j++) {
  62                 if (go[i][j]) {
  63                     baseFlow[i][j] = MAXW;
  64                     baseFlow[s][i] += MAXW;
  65                     baseFlow[j][t] += MAXW;
  66
  67                     cap[i][j] = MAXW - 1;
  68                     cap[s][i] += MAXW;
  69                     cap[j][t] += MAXW;
  70
  71                     flow[i][j] = MAXW - 1;
  72                     flow[j][i] = -(MAXW - 1);
  73
  74                     flow[s][i] += MAXW - 1;
  75                     flow[i][s] -= MAXW - 1;
  76
  77                     flow[j][t] += MAXW - 1;
  78                     flow[t][j] -= MAXW - 1;
  79                 }
  80             }
  81         }
  82
  83         int a = 1 << 20;
  84         n += 2;
  85         mark = new boolean[n];
  86         while (a > 0) {
  87             Arrays.fill(mark, false);
  88             if (dfs(s, t, a)) {
  89                 continue;
  90             }
  91             a = a >> 1;
  92         }
  93         ans = new int[n][n];
  94         for (int i = 0; i < n; i++) {
  95             for (int j = 0; j < n; j++) {
  96                 if (flow[i][j] < 0) {
  97                     ans[i][j] = 0;
  98                 } else {
  99                     ans[i][j] = baseFlow[i][j] - flow[i][j];
 100                 }
 101             }
 102         }
 103
 104         int answer = 0;
 105         for (int i = 0; i < n; i++) {
 106             answer += ans[s][i];
 107         }
 108         out.println(answer);
 109
 110         path = new int[n];
 111         for (int i = 0; i < n; i++) {
 112             while (ans[s][i] > 0) {
 113                 Arrays.fill(mark, false);
 114                 count = 0;
 115                 findPath(s, t);
 116                 for (int j = count - 2; j >= 0; j--) {
 117                     out.print((path[j] + 1) + " ");
 118                 }
 119                 out.println();
 120             }
 121         }
 122     }
 123
 124
 125     private boolean findPath(int u, int target) {
 126         if (u == target) {
 127             return true;
 128         }
 129         mark[u] = true;
 130         for (int v = 0; v < n; v++) {
 131             if (ans[u][v] > 0 && !mark[v] && findPath(v, target)) {
 132                 ans[u][v]--;
 133                 path[count++] = u;
 134                 return true;
 135             }
 136         }
 137         return false;
 138     }
 139
 140     private boolean dfs(int u, int target, int a) {
 141         if (u == target) {
 142             return true;
 143         }
 144         mark[u] = true;
 145         for (int v = 0; v < n; v++) {
 146             if (!mark[v] && flow[u][v] + a <= cap[u][v] && dfs(v, target, a)) {
 147                 flow[u][v] += a;
 148                 flow[v][u] -= a;
 149                 return true;
 150             }
 151         }
 152         return false;
 153     }
 154
 155     public static void main(String[] args) {
 156         new Thread(new inspection_rs()).start();
 157     }
 158
 159     public void run() {
 160         String problem = getClass().getName().split("_")[0];
 161         try {
 162             in = new BufferedReader(new FileReader(new File(problem + ".in")));
 163             out = new PrintWriter(new File(problem + ".out"));
 164             solve();
 165             in.close();
 166             out.close();
 167         } catch (IOException e) {
 168             e.printStackTrace();
 169             System.exit(1);
 170         }
 171     }
 172 }