NEERC/inspection/inspection_petr.java

   1 import java.io.BufferedReader;
   2 import java.io.FileReader;
   3 import java.io.PrintWriter;
   4 import java.io.IOException;
   5 import java.util.StringTokenizer;
   6 import java.util.List;
   7 import java.util.ArrayList;
   8
   9 public class inspection_petr implements Runnable {
  10     static final int INF = 1000000;
  11
  12     private void solve() throws IOException {
  13         int n = nextInt();
  14         boolean[][] e = new boolean[n][n];
  15         int[] ne = new int[n];
  16         List<Integer>[][] paths = new List[n][n];
  17         int res = 0;
  18         for (int i = 0; i < n; ++i) {
  19             int m = nextInt();
  20             paths[i][i] = new ArrayList<Integer>();
  21             for (int j = 0; j < m; ++j) {
  22                 int b = nextInt() - 1;
  23                 e[i][b] = true;
  24                 paths[i][b] = new ArrayList<Integer>();
  25                 paths[i][b].add(b);
  26                 ++ne[i];
  27                 ++res;
  28             }
  29         }
  30         for (int k = 0; k < n; ++k)
  31             for (int i = 0; i < n; ++i)
  32                 for (int j = 0; j < n; ++j)
  33                     if (paths[i][j] == null && paths[i][k] != null && paths[k][j] != null) {
  34                         paths[i][j] = new ArrayList<Integer>();
  35                         paths[i][j].addAll(paths[i][k]);
  36                         paths[i][j].addAll(paths[k][j]);
  37                     }
  38         int[][] c = new int[2 * n + 2][2 * n + 2];
  39         int s = 2 * n;
  40         int t = 2 * n + 1;
  41         for (int i = 0; i < n; ++i)
  42             for (int j = 0; j < n; ++j) {
  43                 if (e[i][j]) {
  44                     ++c[s][j];
  45                     ++c[i + n][t];
  46                 }
  47                 if (paths[i][j] != null) {
  48                     c[i][j + n] = INF;
  49                 }
  50             }
  51         int[][] flow = new int[2 * n + 2][2 * n + 2];
  52         res -= maxFlow(2 * n + 2, s, t, flow, c);
  53         int[] topological = new int[n];
  54         for (int i = 0; i < n; ++i)
  55             topological[i] = -1;
  56         for (int i = 0; i < n; ++i) {
  57             for (int j = 0; j < n; ++j)
  58                 if (ne[j] == 0) {
  59                     --ne[j];
  60                     topological[n - 1 - i] = j;
  61                     for (int k = 0; k < n; ++k)
  62                         if (e[k][j])
  63                             --ne[k];
  64                     break;
  65                 }
  66         }
  67         List<List<Integer>>[] ending = new List[n];
  68         for (int i = 0; i < n; ++i)
  69             ending[i] = new ArrayList<List<Integer>>();
  70         for (int i = 0; i < n; ++i) {
  71             for (int j = 0; j < n; ++j)
  72                 if (e[topological[i]][j]) {
  73                     List<Integer> l = getSome(n, paths, topological[i], ending, flow);
  74                     if (l == null) {
  75                         l = new ArrayList<Integer>();
  76                         l.add(topological[i]);
  77                     }
  78                     l.add(j);
  79                     ending[j].add(l);
  80                 }
  81         }
  82         List<List<Integer>> all = new ArrayList<List<Integer>>();
  83         for (List<List<Integer>> ll : ending)
  84             all.addAll(ll);
  85         if (all.size() != res)
  86             throw new RuntimeException();
  87         writer.println(all.size());
  88         for (List<Integer> l : all) {
  89             boolean first = true;
  90             for (Integer x : l) {
  91                 if (first)
  92                     first = false;
  93                 else
  94                     writer.print(" ");
  95                 writer.print(x + 1);
  96             }
  97             writer.println();
  98         }
  99     }
 100
 101     private List<Integer> getSome(int n, List<Integer>[][] paths, int at, List<List<Integer>>[] ending, int[][] flow) {
 102         for (int i = 0; i < n; ++i)
 103             if (flow[i][at + n] > 0 && !ending[i].isEmpty()) {
 104                 --flow[i][at + n];
 105                 List<Integer> l = ending[i].get(ending[i].size() - 1);
 106                 ending[i].remove(ending[i].size() - 1);
 107                 l.addAll(paths[i][at]);
 108                 return l;
 109             }
 110         return null;
 111     }
 112
 113     private int maxFlow(int n, int s, int t, int[][] flow, int[][] c) {
 114         int res = 0;
 115         while (true) {
 116             int by = dfs(n, s, t, flow, c, new boolean[n], INF);
 117             if (by == 0)
 118                 break;
 119             res += by;
 120         }
 121         return res;
 122     }
 123
 124     private int dfs(int n, int at, int t, int[][] flow, int[][] c, boolean[] mark, int by) {
 125         if (mark[at])
 126             return 0;
 127         mark[at] = true;
 128         if (at == t)
 129             return by;
 130         for (int i = 0; i < n; ++i)
 131             if (flow[at][i] < c[at][i]) {
 132                 int nby = Math.min(by, c[at][i] - flow[at][i]);
 133                 nby = dfs(n, i, t, flow, c, mark, nby);
 134                 if (nby > 0) {
 135                     flow[at][i] += nby;
 136                     flow[i][at] -= nby;
 137                     return nby;
 138                 }
 139             }
 140         return 0;
 141     }
 142     public static void main(String[] args) throws InterruptedException {
 143         Thread thread = new Thread(new inspection_petr());
 144         thread.start();
 145         thread.join();
 146     }
 147
 148     static final String TASK_ID = "inspection";
 149     static final String IN_FILE = TASK_ID + ".in";
 150     static final String OUT_FILE = TASK_ID + ".out";
 151     BufferedReader reader;
 152     StringTokenizer tokenizer;
 153     PrintWriter writer;
 154
 155     public void run() {
 156         try {
 157             reader = new BufferedReader(new FileReader(IN_FILE));
 158             tokenizer = null;
 159             writer = new PrintWriter(OUT_FILE);
 160             solve();
 161             reader.close();
 162             writer.close();
 163         } catch (Exception e) {
 164             e.printStackTrace();
 165             System.exit(1);
 166         }
 167     }
 168
 169     int nextInt() throws IOException {
 170         return Integer.parseInt(nextToken());
 171     }
 172
 173     long nextLong() throws IOException {
 174         return Long.parseLong(nextToken());
 175     }
 176
 177     double nextDouble() throws IOException {
 178         return Double.parseDouble(nextToken());
 179     }
 180
 181     String nextToken() throws IOException {
 182         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
 183             tokenizer = new StringTokenizer(reader.readLine());
 184         }
 185         return tokenizer.nextToken();
 186     }
 187 }