NEERC/inspection/inspection_mb.java

   1 import java.io.FileReader;
   2 import java.io.IOException;
   3 import java.io.PrintWriter;
   4 import java.util.Arrays;
   5 import java.util.Scanner;
   6
   7 public class inspection_mb implements Runnable {
   8     private Scanner in;
   9     private PrintWriter out;
  10
  11     private int numNodes;
  12     private int sourceNode;
  13     private int sinkNode;
  14     private boolean[][] hasArc;
  15     private int[][] resCap;
  16     private int[][] flow;
  17     private int[] visitedFrom;
  18
  19     public static void main(String[] args) {
  20         new Thread(new inspection_mb()).start();
  21     }
  22
  23     private static final int INFINITY = 1000000;
  24
  25     public void run() {
  26         try {
  27             in = new Scanner(new FileReader("inspection.in"));
  28             out = new PrintWriter("inspection.out");
  29
  30             solve();
  31
  32             in.close();
  33             out.close();
  34         } catch (IOException e) {
  35             e.printStackTrace();
  36         }
  37     }
  38
  39     private void solve() {
  40         numNodes = in.nextInt();
  41         sourceNode = numNodes;
  42         sinkNode = numNodes + 1;
  43
  44         hasArc = new boolean[numNodes + 2][];
  45         flow = new int[numNodes + 2][numNodes + 2];
  46         resCap = new int[numNodes + 2][numNodes + 2];
  47         for (int i = 0; i < numNodes; i++) {
  48             hasArc[i] = new boolean[numNodes + 2];
  49             flow[i] = new int[numNodes + 2];
  50             resCap[i] = new int[numNodes + 2];
  51
  52             resCap[sourceNode][i] = INFINITY;
  53             resCap[i][sinkNode] = INFINITY;
  54         }
  55
  56         for (int from = 0; from < numNodes; from++) {
  57             final int numArcsFrom = in.nextInt();
  58             for (int j = 0; j < numArcsFrom; j++) {
  59                 final int to = in.nextInt() - 1;
  60                 hasArc[from][to] = true;
  61                 if (hasArc[from][to]) {
  62                     flow[sourceNode][from]++;
  63                     resCap[sourceNode][from]--;
  64                     flow[from][sourceNode]--;
  65                     resCap[from][sourceNode]++;
  66
  67                     flow[from][to] = 1;
  68                     resCap[from][to] = INFINITY;
  69                     flow[to][from] = -1;
  70
  71                     flow[to][sinkNode]++;
  72                     resCap[to][sinkNode]--;
  73                     flow[sinkNode][to]--;
  74                     resCap[sinkNode][to]++;
  75                 }
  76             }
  77         }
  78
  79         visitedFrom = new int[numNodes + 2];
  80         while (tryAugment());
  81
  82         int numPaths = 0;
  83         for (int i = 0; i < numNodes; i++) {
  84             numPaths += flow[sourceNode][i];
  85         }
  86
  87         out.println(numPaths);
  88
  89         for (;;) {
  90             int i = sourceNode;
  91             int j = traceFlowPath(i);
  92             if (j < 0) {
  93                 break;
  94             }
  95             while (j != sinkNode) {
  96                 out.printf("%d ", j + 1);
  97                 flow[i][j]--;
  98                 flow[j][i]++;
  99                 i = j;
 100                 j = traceFlowPath(i);
 101             }
 102             out.println();
 103         }
 104     }
 105
 106     private int traceFlowPath(int from) {
 107         for (int to = 0; to < numNodes + 2; to++) {
 108             if (flow[from][to] > 0) {
 109                 return to;
 110             }
 111         }
 112         return -1;
 113     }
 114
 115     private boolean tryAugment() {
 116         Arrays.fill(visitedFrom, -1);
 117         augmentDfs(sinkNode, sinkNode);
 118         if (visitedFrom[sourceNode] < 0) {
 119             return false;
 120         }
 121
 122         int i = sourceNode;
 123         while (i != sinkNode) {
 124             int j = visitedFrom[i];
 125
 126             flow[j][i]++;
 127             resCap[j][i]--;
 128
 129             flow[i][j]--;
 130             resCap[i][j]++;
 131
 132             i = j;
 133         }
 134
 135         return true;
 136     }
 137
 138     private void augmentDfs(int where, int from) {
 139         System.out.printf("Trying to aument at where = %d, from = %d\n", where, from);
 140         if (visitedFrom[where] >= 0) {
 141             return;
 142         }
 143         visitedFrom[where] = from;
 144         if (where == sourceNode) {
 145             return;
 146         }
 147         for (int j = 0; j < numNodes + 2; j++) {
 148             if (resCap[where][j] > 0) {
 149                 augmentDfs(j, where);
 150             }
 151         }
 152     }
 153 }