| 96 | } |
| 97 | |
| 98 | private static int dfsBlocking(int[][] residual, int[] level, int[] next, int u, int sink, int f) { |
| 99 | if (u == sink) { |
| 100 | return f; |
| 101 | } |
| 102 | final int n = residual.length; |
| 103 | for (int v = next[u]; v < n; v++, next[u] = v) { |
| 104 | if (residual[u][v] <= 0) { |
| 105 | continue; |
| 106 | } |
| 107 | if (level[v] != level[u] + 1) { |
| 108 | continue; |
| 109 | } |
| 110 | int pushed = dfsBlocking(residual, level, next, v, sink, Math.min(f, residual[u][v])); |
| 111 | if (pushed > 0) { |
| 112 | residual[u][v] -= pushed; |
| 113 | residual[v][u] += pushed; |
| 114 | return pushed; |
| 115 | } |
| 116 | } |
| 117 | return 0; |
| 118 | } |
| 119 | } |