NEERC/inspection/inspection_pm.java

   1 import java.util.Scanner;
   2 import java.util.Arrays;
   3 import java.io.File;
   4 import java.io.FileNotFoundException;
   5 import java.io.PrintWriter;
   6
   7 public class inspection_pm {
   8
   9     private static int[][] f;
  10     private static boolean[] z;
  11     private static int n;
  12     private static int nn;
  13     private static int[][] c;
  14     private static int[][] aa;
  15
  16     public static void main(String[] args) throws FileNotFoundException {
  17         Scanner in = new Scanner(new File("inspection.in"));
  18         PrintWriter out = new PrintWriter("inspection.out");
  19
  20         n = in.nextInt();
  21         boolean[][] a = new boolean[n][n];
  22         for (int i = 0; i < n; i++) {
  23             int k = in.nextInt();
  24             for (int j = 0; j < k; j++) {
  25                 int x = in.nextInt();
  26                 a[i][x - 1] = true;
  27             }
  28         }
  29
  30         boolean[][] b = new boolean[n][n];
  31         for (int i = 0; i < n; i++) {
  32             System.arraycopy(a[i], 0, b[i], 0, n);
  33         }
  34         for (int i = 0; i < n; i++) {
  35             for (int j = 0; j < n; j++) {
  36                 for (int k = 0; k < n; k++) {
  37                     b[j][k] = b[j][k] || b[j][i] && b[i][k];
  38                 }
  39             }
  40         }
  41
  42         int[] d = new int[n];
  43         for (int i = 0; i < n; i++) {
  44             for (int j = 0; j < n; j++) {
  45                 if (a[i][j]) {
  46                     d[i]++;
  47                     d[j]--;
  48                 }
  49             }
  50         }
  51
  52         nn = 2 * n + 2;
  53         c = new int[nn][nn];
  54         f = new int[nn][nn];
  55
  56         int s = 0;
  57         for (int i = 0; i < n; i++) {
  58             if (d[i] < 0) {
  59                 c[0][i + 2] = -d[i];
  60             }
  61             if (d[i] > 0) {
  62                 c[i + 2 + n][1] = d[i];
  63                 s += d[i];
  64             }
  65         }
  66         for (int i = 0; i < n; i++) {
  67             for (int j = 0; j < n; j++) {
  68                 if (b[i][j]) {
  69                     c[i + 2][j + 2 + n] = 1000000000;
  70                 }
  71             }
  72         }
  73
  74         z = new boolean[nn];
  75         while (dfs(0)) {
  76             Arrays.fill(z, false);
  77             s--;
  78         }
  79
  80         aa = new int[n][n];
  81         for (int i = 0; i < n; i++) {
  82             for (int j = 0; j < n; j++) {
  83                 if (a[i][j]) aa[i][j] = 1;
  84             }
  85         }
  86
  87         z = new boolean[n];
  88         for (int i = 0; i < n; i++) {
  89             for (int j = 0; j < n; j++) {
  90                 for (int k = 0; k < f[i + 2][j + 2 + n]; k++) {
  91                     Arrays.fill(z, false);
  92                     if (!addPath(i, j)) {
  93                         System.out.println("!!!");
  94                     }
  95                     d[i]++;
  96                     d[j]--;
  97                 }
  98             }
  99         }
 100
 101         out.println(s);
 102         for (int i = 0; i < n; i++) {
 103             while (d[i] > 0) {
 104                 d[i]--;
 105                 int k = i;
 106                 while (true) {
 107                     out.print(k + 1);
 108                     out.print(" ");
 109                     for (int kk = 0; kk < n; kk++) {
 110                         if (aa[k][kk] > 0) {
 111                             aa[k][kk]--;
 112                             k = kk;
 113                             break;
 114                         }
 115                     }
 116                     if (d[k] < 0) {
 117                         d[k]++;
 118                         out.println(k + 1);
 119                         break;
 120                     }
 121                 }
 122             }
 123         }
 124
 125         in.close();
 126         out.close();
 127     }
 128
 129     private static boolean addPath(int i, int j) {
 130         if (z[i]) return false;
 131         z[i] = true;
 132         if (i == j) {
 133             return true;
 134         }
 135         for (int x = 0; x < n; x++) if (aa[i][x] > 0) {
 136             if (addPath(x, j)) {
 137                 aa[i][x]++;
 138                 return true;
 139             }
 140         }
 141         return false;
 142     }
 143
 144     private static boolean dfs(int i) {
 145         if (z[i]) return false;
 146         z[i] = true;
 147         if (i == 1) {
 148             return true;
 149         }
 150         for (int j = 0; j < nn; j++) {
 151             if (f[i][j] < c[i][j]) {
 152                 if (dfs(j)) {
 153                     f[i][j]++;
 154                     f[j][i]--;
 155                     return true;
 156                 }
 157             }
 158         }
 159         return false;
 160     }
 161 }